Skip to Content

Instrukcja korzystania z Biblioteki


Ukryty Internet | Wyszukiwarki specjalistyczne tekstów i źródeł naukowych | Translatory online | Encyklopedie i słowniki online


Astronomia Astrofizyka

Sztuka dawna i współczesna, muzea i kolekcje

Metodologia nauk, Matematyka, Filozofia, Miary i wagi, Pomiary

Substancje, reakcje, energia
Fizyka, chemia i inżynieria materiałowa

Antropologia kulturowa Socjologia Psychologia Zdrowie i medycyna

Przewidywania Kosmologia Religie Ideologia Polityka

Geologia, geofizyka, geochemia, środowisko przyrodnicze

Biologia, biologia molekularna i genetyka

Technologia cyberprzestrzeni, cyberkultura, media i komunikacja

Wiadomości | Gospodarka, biznes, zarządzanie, ekonomia

Budownictwo, energetyka, transport, wytwarzanie, technologie informacyjne

Referaty z Computer Science na

This paper considers the problem of networks reconstruction from
heterogeneous data using a Gaussian Graphical Mixture Model (GGMM). It is well
known that parameter estimation in this context is challenging due to large
numbers of variables coupled with the degeneracy of the likelihood. We propose
as a solution a penalized maximum likelihood technique by imposing an $l_{1}$
penalty on the precision matrix. Our approach shrinks the parameters thereby
resulting in better identifiability and variable selection. We use the
Expectation Maximization (EM) algorithm which involves the graphical LASSO to
estimate the mixing coefficients and the precision matrices. We show that under
certain regularity conditions the Penalized Maximum Likelihood (PML) estimates
are consistent. We demonstrate the performance of the PML estimator through
simulations and we show the utility of our method for high dimensional data
analysis in a genomic application. 2013/08/16 - 21:07

We investigate axioms that intuitively ought to be satisfied by graph
clustering objective functions. Two tailored for graph clustering objectives
are introduced, and the four axioms introduced in previous work on distance
based clustering are reformulated and generalized for the graph setting. We
show that modularity, a standard objective for graph clustering, does not
satisfy all these axioms. This leads us to consider adaptive scale modularity,
a variant of modularity, that does satisfy the axioms. Adaptive scale
modularity has two parameters, which give greater control over the clustering.
Standard graph clustering objectives, such as normalized cut and unnormalized
cut, are obtained as special cases of adaptive scale modularity. We furthermore
show that adaptive scale modularity does not have a resolution limit. In
general, the results of our investigation indicate that the considered axioms
cover existing `good' objective functions for graph clustering, and can be used
to derive an interesting new family of objectives. 2013/08/16 - 21:07

In this paper we analyze the probability of consistency of sensor data
distribution systems (SDDS), and determine suitable evaluation models. This
problem is typically difficult, since a reliable model taking into account all
parameters and processes which affect the system consistency is unavoidably
very complex. The simplest candidate approach consists of modeling the state
sojourn time, or holding time, as memoryless, and resorting to the well known
solutions of Markovian processes. Nevertheless, it may happen that this
approach does not fit with some working conditions. In particular, the correct
modeling of the SDDS dynamics requires the introduction of a number of
parameters, such as the packet transfer time or the packet loss probability,
the value of which may determine the suitability of unsuitability of the
Markovian model. Candidate alternative solutions include the Erlang phase-type
approximation of nearly constant state holding time and a more refined model to
account for overlapping events in semi-Markov processes. 2013/08/16 - 21:07

We present a deterministic model for on-line social networks (OSNs) based on
transitivity and local knowledge in social interactions. In the Iterated Local
Transitivity (ILT) model, at each time-step and for every existing node $x$, a
new node appears which joins to the closed neighbour set of $x.$ The ILT model
provably satisfies a number of both local and global properties that were
observed in OSNs and other real-world complex networks, such as a densification
power law, decreasing average distance, and higher clustering than in random
graphs with the same average degree. Experimental studies of social networks
demonstrate poor expansion properties as a consequence of the existence of
communities with low number of inter-community edges. Bounds on the spectral
gap for both the adjacency and normalized Laplacian matrices are proved for
graphs arising from the ILT model, indicating such bad expansion properties.
The cop and domination number are shown to remain the same as the graph from
the initial time-step $G_0$, and the automorphism group of $G_0$ is a subgroup
of the automorphism group of graphs generated at all later time-steps. A
randomized version of the ILT model is presented, which exhibits a tuneable
densification power law exponent, and maintains several properties of the
deterministic model. 2013/08/16 - 21:07

Self-organization of heterogeneous particle swarms is rich in its dynamics
but hard to design in a traditional top-down manner, especially when many types
of kinetically distinct particles are involved. In this chapter, we discuss how
we have been addressing this problem by (1) utilizing and enhancing interactive
evolutionary design methods and (2) realizing spontaneous evolution of self
organizing swarms within an artificial ecosystem. 2013/08/16 - 21:07

Recently a number of randomized 3/4-approximation algorithms for MAX SAT have
been proposed that all work in the same way: given a fixed ordering of the
variables, the algorithm makes a random assignment to each variable in
sequence, in which the probability of assigning each variable true or false
depends on the current set of satisfied (or unsatisfied) clauses. To our
knowledge, the first such algorithm was proposed by Poloczek and Schnitger; Van
Zuylen subsequently gave an algorithm that set the probabilities differently
and had a simpler analysis. She also set up a framework for deriving such
algorithms. Buchbinder, Feldman, Naor, and Schwartz, as a special case of their
work on maximizing submodular functions, also give a randomized
3/4-approximation algorithm for MAX SAT with the same structure as these
previous algorithms. In this note we give a gloss on the Buchbinder et al.
algorithm that makes it even simpler, and show that in fact it is equivalent to
the previous algorithm of Van Zuylen. We also show how it extends to a
deterministic LP rounding algorithm; such an algorithm was also given by Van
Zuylen. 2013/08/16 - 21:07

In this primer, we will describe a number of projects that can be completed
with a 3D printer, particularly by mathematics professors and their students.
For many of the projects, we will utilize Mathematica to design objects that
mathematicians may be interested in printing. Included in the projects that are
described is a method to acquire data from an XBox Kinect. 2013/08/16 - 21:07

Stochastic neurons and hard non-linearities can be useful for a number of
reasons in deep learning models, but in many cases they pose a challenging
problem: how to estimate the gradient of a loss function with respect to the
input of such stochastic or non-smooth neurons? I.e., can we "back-propagate"
through these stochastic neurons? We examine this question, existing
approaches, and compare four families of solutions, applicable in different
settings. One of them is the minimum variance unbiased gradient estimator for
stochatic binary neurons (a special case of the REINFORCE algorithm). A second
approach, introduced here, decomposes the operation of a binary stochastic
neuron into a stochastic binary part and a smooth differentiable part, which
approximates the expected effect of the pure stochatic binary neuron to first
order. A third approach involves the injection of additive or multiplicative
noise in a computational graph that is otherwise differentiable. A fourth
approach heuristically copies the gradient with respect to the stochastic
output directly as an estimator of the gradient with respect to the sigmoid
argument (we call this the straight-through estimator). To explore a context
where these estimators are useful, we consider a small-scale version of {\em
conditional computation}, where sparse stochastic units form a distributed
representation of gaters that can turn off in combinatorially many ways large
chunks of the computation performed in the rest of the neural network. In this
case, it is important that the gating units produce an actual 0 most of the
time. The resulting sparsity can be potentially be exploited to greatly reduce
the computational cost of large deep networks for which conditional computation
would be useful. 2013/08/16 - 21:07

Identification of communities in complex networks has become an effective
means to analysis of complex systems. It has broad applications in diverse
areas such as social science, engineering, biology and medicine. Finding
communities of nodes and finding communities of links are two popular schemes
for network structure analysis. These schemes, however, have inherent drawbacks
and are often inadequate to properly capture complex organizational structures
in real networks. We introduce a new scheme and effective approach for
identifying complex network structures using a mixture of node and link
communities, called hybrid node-link communities. A central piece of our
approach is a probabilistic model that accommodates node, link and hybrid
node-link communities. Our extensive experiments on various real-world
networks, including a large protein-protein interaction network and a large
semantic association network of commonly used words, illustrated that the
scheme for hybrid communities is superior in revealing network characteristics.
Moreover, the new approach outperformed the existing methods for finding node
or link communities separately. 2013/08/16 - 21:07

In the Palindrome Problem one tries to find all palindromes (palindromic
substrings) in a given string. A palindrome is defined as a string which reads
forwards the same as backwards, e.g., the string "racecar". A related problem
is the Longest Palindromic Substring Problem in which finding an arbitrary one
of the longest palindromes in the given string suffices. We regard the
streaming version of both problems. In the streaming model the input arrives
over time and at every point in time we are only allowed to use sublinear
space. The main algorithms in this paper are the following: The first one is a
one-pass randomized algorithm that solves the Palindrome Problem. It has an
additive error and uses $O(\sqrt n$) space. The second algorithm is a two-pass
algorithm which determines the exact locations of all longest palindromes. It
uses the first algorithm as the first pass. The third algorithm is again a
one-pass randomized algorithm, which solves the Longest Palindromic Substring
Problem. It has a multiplicative error using only $O(\log(n))$ space. We also
give two variants of the first algorithm which solve other related practical
problems. 2013/08/16 - 21:07

We show how security type systems from the literature of language-based
noninterference can be represented more directly as predicates defined by
structural recursion on the programs. In this context, we show how our uniform
syntactic criteria from previous work cover several previous type-system
soundness results. 2013/08/16 - 21:07

Every device defines the behavior of various applications running on it with
the help of user profiles or settings. What if a user wants different different
applications to run in different different networks. Then he cannot do this
because in todays existing operating systems the application profile, user
specific tool settings and any such system usage settings do not consider the
current network characteristics of the user or system and are therefore static
in nature.Therefore there is a need for an intelligent system which will
dynamically change or apply changes to the settings of various applications
running on the system considering the current network characteristics based on
user specifications. This paper presents an idea such that a user can set
different different applications in different different networks.This paper
presents how the user will get pop up messages when he visits to safe web
sites. And according to the users current network status he will get a pop up
message when he will go for download or stream audio or video files. 2013/08/16 - 21:07

User credentials security is one of the most important tasks in Web World.
Most Web sites on the Internet that support user accounts store the users
credentials in a database. Now a days, most of the web browsers offer auto
login feature for the favorite web sites such as yahoo, google, gmail etc.
using these credential information. This facilitates the misuse of user
credentials. Privatizing user credential information of web services in a
shared user environment provides a feature enhancement where the root user will
be able to privatize his stored credentials by enforcing some masking
techniques such that even a user logs on to the system with root user
credentials, he will not be able to access privatized data. In case of web
browsers auto login feature, a root user can disable the feature manually by
deleting entries from web browsers' saved password list. But this involves
spending a considerable amount of time and the biggest problem is that he has
to insert those credentials once again when he next visits these websites. This
application resumes auto login feature whenever root user disable the masked
mode. The application includes two parts: Masked Application Mode and Disabling
the Masked Application Mode. When the system goes for masked application mode,
the other user will not be able to use the credentials of the root user.If the
other user tries to access any of the web pages which have been masked, the
other user will have to authenticate with his own credentials. Disabling the
masked mode requires authentication from the root user. As long as this
credential is not shared, masked mode can be disabled only by the root user. 2013/08/16 - 21:07

More often than not, bad decisions are bad regardless of where and when they
are made. Information sharing might thus be utilized to mitigate them. Here we
show that sharing the information about strategy choice between players
residing on two different networks reinforces the evolution of cooperation. In
evolutionary games the strategy reflects the action of each individual that
warrants the highest utility in a competitive setting. We therefore assume that
identical strategies on the two networks reinforce themselves by lessening
their propensity to change. Besides network reciprocity working in favour of
cooperation on each individual network, we observe the spontaneous emerge of
correlated behaviour between the two networks, which further deters defection.
If information is shared not just between individuals but also between groups,
the positive effect is even stronger, and this despite the fact that
information sharing is implemented without any assumptions with regards to
content. 2013/08/16 - 21:07

We assume data sampled from a mixture of d-dimensional linear subspaces with
spherically symmetric distributions within each subspace and an additional
outlier component with spherically symmetric distribution within the ambient
space (for simplicity we may assume that all distributions are uniform on their
corresponding spheres). We also assume mixture weights for the different
components. We say that one of the underlying subspaces of the model is most
significant if its mixture weight is higher than the sum of the mixture weights
of all other subspaces. We study the recovery of the most significant subspace
by minimizing the lp-averaged distances of data points from d-dimensional
subspaces, where p>0. Unlike other lp minimization problems, this minimization
is non-convex for all p>0 and thus requires different methods for its analysis.
We show that if 0<p<=1, then for any fraction of outliers the most significant
subspace can be recovered by lp minimization with overwhelming probability
(which depends on the generating distribution and its parameters). We show that
when adding small noise around the underlying subspaces the most significant
subspace can be nearly recovered by lp minimization for any 0<p<=1 with an
error proportional to the noise level. On the other hand, if p>1 and there is
more than one underlying subspace, then with overwhelming probability the most
significant subspace cannot be recovered or nearly recovered. This last result
does not require spherically symmetric outliers. 2013/08/16 - 21:07

The two-way continuous-variable quantum key distribution (CVQKD) systems
allow higher key rates and improved transmission distances over standard
telecommunication networks in comparison to the one-way CVQKD protocols. To
exploit the real potential of two-way CVQKD systems a robust reconciliation
technique is needed. It is currently unavailable, which makes it impossible to
reach the real performance of a two-way CVQKD system. The reconciliation
process of correlated Gaussian variables is a complex problem that requires
either tomography in the physical layer that is intractable in a practical
scenario, or high-cost calculations in the multidimensional spherical space
with strict dimensional limitations. To avoid these issues, we propose an
efficient logical layer-based reconciliation method for two-way CVQKD to
extract binary information from correlated Gaussian variables. We demonstrate
that by operating on the raw-data level, the noise of the quantum channel can
be corrected in the scalar space and the reconciliation can be extended to
arbitrary high dimensions. We prove that the error probability of scalar
reconciliation is zero in any practical CVQKD scenario, and provides
unconditional security. The results allow to significantly improve the
currently available key rates and transmission distances of two-way CVQKD. The
proposed scalar reconciliation can also be applied in one-way systems as well,
to replace the existing reconciliation schemes. 2013/08/15 - 11:24

This paper provides necessary conditions and sufficient conditions for the
(global) Input-to-State Stability property of simple uncertain
vehicular-traffic network models under the effect of a PI-regulator. Local
stability properties for vehicular-traffic networks under the effect of
PI-regulator control are studied as well: the region of attraction of a locally
exponentially stable equilibrium point is estimated by means of Lyapunov
functions. All obtained results are illustrated by means of simple examples. 2013/08/14 - 10:07

Linearizability is a commonly accepted notion of correctness for libraries of
concurrent algorithms. Unfortunately, it assumes a complete isolation between a
library and its client, with interactions limited to passing values of a given
data type. This is inappropriate for common programming languages, where
libraries and their clients can communicate via the heap, transferring the
ownership of data structures, and can even run in a shared address space
without any memory protection.

In this paper, we present the first definition of linearizability that lifts
this limitation and establish an Abstraction Theorem: while proving a property
of a client of a concurrent library, we can soundly replace the library by its
abstract implementation related to the original one by our generalisation of
linearizability. This allows abstracting from the details of the library
implementation while reasoning about the client. We also prove that
linearizability with ownership transfer can be derived from the classical one
if the library does not access some of data structures transferred to it by the
client. 2013/08/14 - 10:07

The present paper suggests a new approach for geometric representation of 3D
spatial models and provides a new compression algorithm for 3D meshes, which is
based on mathematical theory of convex geometry. In our approach we represent a
3D convex polyhedron by means of planes, containing only its faces. This allows
not to consider topological aspects of the problem (connectivity information
among vertices and edges) since by means of the planes we construct the
polyhedron uniquely. Due to the fact that the topological data is ignored this
representation provides high degree of compression. Also planes based
representation provides a compression of geometrical data because most of the
faces of the polyhedron are not triangles but polygons with more than three
vertices. 2013/08/14 - 10:07

Power-law correlations have been observed in packet flow over the Internet.
The possible origin of these correlations includes demand for Internet
services. We observe the demand for e-mail services in an organization, and
analyze correlations in the flow and the sequence of send requests using a
Detrended Fluctuation Analysis (DFA). The correlation in the flow is found to
be weaker than that in the send requests. Four types of artificial flow are
constructed to investigate the effects of fluctuations in e-mail sizes. As a
result, we find that the correlation in the flow originates from that in the
sequence of send requests. The strength of the power-law correlation decreases
as a function of the ratio of the standard deviation of e-mail sizes to their
average. 2013/08/14 - 10:07

A translation from Russian of the work of R.R. Kamalian "Interval colorings
of complete bipartite graphs and trees", Preprint of the Computing Centre of
the Academy of Sciences of Armenia, Yerevan, 1989. (Was published by the
decision of the Academic Council of the Computing Centre of the Academy of
Sciences of Armenian SSR and Yerevan State University from 7.09.1989). 2013/08/14 - 10:07

The focused organization theory of social ties proposes that the structure of
human social networks can be arranged around extra-network foci, which can
include shared physical spaces such as homes, workplaces, restaurants, and so
on. Until now, this has been difficult to investigate on a large scale, but the
huge volume of data available from online location-based social services now
makes it possible to examine the friendships and mobility of many thousands of
people, and to investigate the relationship between meetings at places and the
structure of the social network. In this paper, we analyze a large dataset from
Foursquare, the most popular online location-based social network. We examine
the properties of city-based social networks, finding that they have common
structural properties, and that the category of place where two people meet has
very strong influence on the likelihood of their being friends. Inspired by
these observations in combination with the focused organization theory, we then
present a model to generate city-level social networks, and show that it
produces networks with the structural properties seen in empirical data. 2013/08/14 - 10:07

Stochastic simulation techniques employed for the analysis of portfolios of
insurance/reinsurance risk, often referred to as `Aggregate Risk Analysis', can
benefit from exploiting state-of-the-art high-performance computing platforms.
In this paper, parallel methods to speed-up aggregate risk analysis for
supporting real-time pricing are explored. An algorithm for analysing aggregate
risk is proposed and implemented for multi-core CPUs and for many-core GPUs.
Experimental studies indicate that GPUs offer a feasible alternative solution
over traditional high-performance computing systems. A simulation of 1,000,000
trials with 1,000 catastrophic events per trial on a typical exposure set and
contract structure is performed in less than 5 seconds on a multiple GPU
platform. The key result is that the multiple GPU implementation can be used in
real-time pricing scenarios as it is approximately 77x times faster than the
sequential counterpart implemented on a CPU. 2013/08/14 - 10:07

In vehicular ad-hoc networks (VANETs) the impact of vehicles as obstacles has
largely been neglected in the past. Recent studies have reported that the
vehicles that obstruct the line-of-sight (LOS) path may introduce 10-20,dB
additional loss, and as a result reduce the communication range. Most of the
traffic mobility models (TMM) today do not treat other vehicles as obstacles
and thus can not model the impact of LOS obstruction in VANET simulations. In
this paper the LOS obstruction caused by other vehicles is studied in a highway
scenario. First a car-following model is used to characterize the motion of the
vehicles driving in the same direction on a two-lane highway. Vehicles are
allowed to change lanes when necessary. The position of each vehicle is updated
by using car-following rules together with the lane-changing rules for the
forward motion. Based on the simulated traffic a simple TMM is proposed for
VANET simulations, which is capable to identify the vehicles that are in the
shadow region of other vehicles. The presented traffic mobility model together
with the shadow fading path loss model can take in to account the impact of LOS
obstruction on the total received power in the two-lane highway scenarios. 2013/08/14 - 10:07

This paper studies the mechanisms, implications, and potential applications
of the recently discovered class of Zero Determinant (ZD) strategies in
iterated 2x2 games. These strategies were reported to successfully extort pure
economic maximizers, and to mischievously determine the set of feasible
long-term payoffs in iterated Prisoners' Dilemma by enforcing linear
constraints on both players' expected average scores.

These results are generalized for all symmetric 2x2 games and a general
Battle of the Sexes, exemplified by four common games. Additionally, a
comparison to conventional strategies is made and typical ZD gameplay
simulations are analyzed along with convergence speeds. Several response
strategies are discussed, including a glance on how time preferences change
previous results. Furthermore, a possibility of retaliation is presented: when
maximin scores exceed the minimum symmetric payoff, it is possible to extort
the extortioner.

Finally, a summary of findings from evolutionary game theory shows that
mischief is limited by its own malice. Nevertheless, this does not challenge
the result that mindless economic maximization is subject to extortion: the
study of ZD strategies reveals exciting new perspectives and opportunities in
game theory, both evolutionary and classic. 2013/08/14 - 10:07

In CNC manufacturing,there often arises the need to create G-Code programs
which require the calculation of discrete x-y coordinate pairs(2D).An example
of this situation is when the programmer needs to create a program to machine a
helix(or thread).The required toolpath will be a set of points on a helix
curve.The problem now entails calculating the number of points along this
curve.Too few points and the toolpath will not be smooth.Too many points and
the program becomes too big.This article will serve to provide a simple way to
divide a circle into discrete points,with a notion of "dimensional tolerance"
built into the algorithm. 2013/08/14 - 10:07

A class of centrality measures called betweenness centralities reflects
degree of participation of edges or nodes in communication between different
parts of the network. The original shortest-path betweenness centrality is
based on counting shortest paths which go through a node or an edge. One of
shortcomings of the shortest-path betweenness centrality is that it ignores the
paths that might be one or two steps longer than the shortest paths, while the
edges on such paths can be important for communication processes in the
network. To rectify this shortcoming a current flow betweenness centrality has
been proposed. Similarly to the shortest path betwe has prohibitive complexity
for large size networks. In the present work we propose two regularizations of
the current flow betweenness centrality, \alpha-current flow betweenness and
truncated \alpha-current flow betweenness, which can be computed fast and
correlate well with the original current flow betweenness. 2013/08/14 - 10:07

In this article, we consider remote-controlled systems, where the command
generator and the controlled object are connected with a bandwidth-limited
communication link. In the remote-controlled systems, efficient representation
of control commands is one of the crucial issues because of the bandwidth
limitations of the link. We propose a new representation method for control
commands based on compressed sensing. In the proposed method, compressed
sensing reduces the number of bits in each control signal by representing it as
a sparse vector. The compressed sensing problem is solved by an L1-L2
optimization, which can be effectively implemented with an iterative shrinkage
algorithm. A design example also shows the effectiveness of the proposed
method. 2013/08/14 - 10:07

Research opportunities may be lost as the needed knowledge is often hidden
behind a paywall and may not be accessible for many researchers due to the
rising subscription costs of journals. Arguably, a solution for this issue
would be to make all research results barrier-free, available on the Internet.
Open Access (OA) is such an initiative. In Software Engineering (SE) and
Information Systems (IS) fields, however, OA journals are recently born,
limited in number, and largely unknown by researchers. [..] This paper is a
contribution towards an understanding of OA publishing in the fields of SE and
IS. The study proposes an analysis framework of 18 core attributes, divided
into the areas of Identification, Publication Metrics, Economics,
Accessibility, and Trustworthiness of OA journals. The framework is employed in
a systematic analysis of 30 OA journals in SE and IS, which were selected among
386 OA journals in Computer Science, listed in the Directory of OA Journals
(DOAJ). [..] This article offers several contributions. It (1) presents a
detailed overview of OA definitions and publishing models. (2) raises the need
to study OA in the fields of SE and IS while informing the reader of the
existence of 30 journals. (3) offers a detailed comparison of the journals and
analyzes the issues of OA publishing. Most significantly, it (4) provides an
analysis framework born from the observation of data and the literature. (5)
provides useful recommendations to readers, authors, and publishers of OA
articles and journals. It demonstrates that high publication charges are not
sufficiently justified by the publishers, which lack transparency and may
prevent authors from adopting OA. OA is threatened by numerous issues. This
paper aims to highlight such issues with the hope that in the near future, OA
can be studied as a real alternative to traditional publishing systems for SE
and IS fields. 2013/08/14 - 10:07

The Directed Rural Postman Problem (DRPP) can be formulated as follows: given
a connected directed multigraph $G=(V,A)$ with nonnegative weights on the arcs,
a subset $R$ of $A$ and a number $\ell$, decide whether $G$ has a closed
directed walk containing every arc of $R$ and of total weight at most $\ell$.
Let $c$ be the number of components in the underlying undirected graph of
$G[R]$, where $G[R]$ is the subgraph of $G$ induced by $R$. Sorge et al. (2012)
ask whether the DRPP is fixed-parameter tractable (FPT) when parameterized by
$c$, i.e., whether there is an algorithm (called a fixed-parameter algorithm)
of running time $f(c)p^{O(1)},$ where $f$ is a function of $c$ only and $p$ is
the number of vertices in $G$. Sorge et al. (2012) note that this question is
of significant practical relevance and has been open for more than thirty

Sorge et al. (2012) showed that DRPP is FPT-equivalent to the following
problem called the Conjoining Bipartite Matching (CBM) problem: given a
bipartite graph $B$ with nonnegative weights on its edges, a partition $V_1\cup
... \cup V_t$ of vertices of $B$ and a graph $(\{1,..., t\},F)$, and the
parameter $|F|$, decide whether $B$ contains a perfect matching $M$ such that
for each $ij\in F$ there is an edge $uv\in M$ such that $u\in V_i$ and $v\in
V_j$. We may assume that both partite sets of $B$ have the same number $n$ of
vertices. We prove that there is a randomized algorithm for CBM of running time
$2^{|F|}n^{O(1)}$, provided the total weight of $B$ is bounded by a polynomial
in $n$. By our result for CBM and FPT-reductions of Sorge et al. (2012) and
Dorn et al. (2013), DRPP has a randomized fixed-parameter algorithm, provided
the total weight of $B$ is bounded by a polynomial in $p$. 2013/08/14 - 10:07

When different type of packets with different needs of Quality of Service
(QoS) requirements share the same network resources, it became important to use
queue management and scheduling schemes in order to maintain perceived quality
at the end users at an acceptable level. Many schemes have been studied in the
literature, these schemes use time priority (to maintain QoS for Real Time (RT)
packets) and/or space priority (to maintain QoS for Non Real Time (NRT)
packets). In this paper, we study and show the drawback of a combined time and
space priority (TSP) scheme used to manage QoS for RT and NRT packets intended
for an end user in High Speed Downlink Packet Access (HSDPA) cell, and we
propose an enhanced scheme (Enhanced Basic-TSP scheme) to improve QoS
relatively to the RT packets, and to exploit efficiently the network resources.
A mathematical model for the EB-TSP scheme is done, and numerical results show
the positive impact of this scheme. 2013/08/14 - 10:07

We present a series of almost settled inapproximability results for three
fundamental problems. The first in our series is the subexponential-time
inapproximability of the maximum independent set problem, a question studied in
the area of parameterized complexity. The second is the hardness of
approximating the maximum induced matching problem on bounded-degree bipartite
graphs. The last in our series is the tight hardness of approximating the
k-hypergraph pricing problem, a fundamental problem arising from the area of
algorithmic game theory. In particular, assuming the Exponential Time
Hypothesis, our two main results are:

- For any r larger than some constant, any r-approximation algorithm for the
maximum independent set problem must run in at least
2^{n^{1-\epsilon}/r^{1+\epsilon}} time. This nearly matches the upper bound of
2^{n/r} (Cygan et al., 2008). It also improves some hardness results in the
domain of parameterized complexity (e.g., Escoffier et al., 2012 and Chitnis et
al., 2013)

- For any k larger than some constant, there is no polynomial time min
(k^{1-\epsilon}, n^{1/2-\epsilon})-approximation algorithm for the k-hypergraph
pricing problem, where n is the number of vertices in an input graph. This
almost matches the upper bound of min (O(k), \tilde O(\sqrt{n})) (by Balcan and
Blum, 2007 and an algorithm in this paper).

We note an interesting fact that, in contrast to n^{1/2-\epsilon} hardness
for polynomial-time algorithms, the k-hypergraph pricing problem admits
n^{\delta} approximation for any \delta >0 in quasi-polynomial time. This puts
this problem in a rare approximability class in which approximability
thresholds can be improved significantly by allowing algorithms to run in
quasi-polynomial time. 2013/08/14 - 10:07

This paper reports on a study in which a novel virtual moving sound-based
spatial auditory brain-computer interface (BCI) paradigm is developed. Classic
auditory BCIs rely on spatially static stimuli, which are often boring and
difficult to perceive when subjects have non-uniform spatial hearing perception
characteristics. The concept of moving sound proposed and tested in the paper
allows for the creation of a P300 oddball paradigm of necessary target and
non-target auditory stimuli, which are more interesting and easier to
distinguish. We present a report of our study of seven healthy subjects, which
proves the concept of moving sound stimuli usability for a novel BCI. We
compare online BCI classification results in static and moving sound paradigms
yielding similar accuracy results. The subject preference reports suggest that
the proposed moving sound protocol is more comfortable and easier to
discriminate with the online BCI. 2013/08/14 - 10:07

Early tumor detection is key in reducing the number of breast cancer death
and screening mammography is one of the most widely available and reliable
method for early detection. However, it is difficult for the radiologist to
process with the same attention each case, due the large amount of images to be
read. Computer aided detection (CADe) systems improve tumor detection rate; but
the current efficiency of these systems is not yet adequate and the correct
interpretation of CADe outputs requires expert human intervention. Computer
aided diagnosis systems (CADx) are being designed to improve cancer diagnosis
accuracy, but they have not been efficiently applied in breast cancer. CADx
efficiency can be enhanced by considering the natural mirror symmetry between
the right and left breast. The objective of this work is to evaluate
co-registration algorithms for the accurate alignment of the left to right
breast for CADx enhancement. A set of mammograms were artificially altered to
create a ground truth set to evaluate the registration efficiency of DEMONs,
and SPLINE deformable registration algorithms. The registration accuracy was
evaluated using mean square errors, mutual information and correlation. The
results on the 132 images proved that the SPLINE deformable registration
over-perform the DEMONS on mammography images. 2013/08/14 - 10:07

This paper investigates the control of an ML component within the Covariance
Matrix Adaptation Evolution Strategy (CMA-ES) devoted to black-box
optimization. The known CMA-ES weakness is its sample complexity, the number of
evaluations of the objective function needed to approximate the global optimum.
This weakness is commonly addressed through surrogate optimization, learning an
estimate of the objective function a.k.a. surrogate model, and replacing most
evaluations of the true objective function with the (inexpensive) evaluation of
the surrogate model. This paper presents a principled control of the learning
schedule (when to relearn the surrogate model), based on the Kullback-Leibler
divergence of the current search distribution and the training distribution of
the former surrogate model. The experimental validation of the proposed
approach shows significant performance gains on a comprehensive set of
ill-conditioned benchmark problems, compared to the best state of the art
including the quasi-Newton high-precision BFGS method. 2013/08/14 - 10:07

Let $w$ be a word in alphabet $\{x,D\}$. Interpreting "$x$" as multiplication
by $x$, and "$D$" as differentiation with respect to $x$, the identity $$ wf(x)
= x^{(#({$x$'s in $w$})-#({$D$'s in $w$}))}\sum_k S_w(k) x^k D^k f(x), $$ valid
for any smooth function $f(x)$, defines a sequence $(S_w(k))_k$, the terms of
which we refer to as the {\em Stirling numbers (of the second kind)} of $w$.
The nomenclature comes from the fact that when $w=(xD)^n$, we have $S_w(k)={n
\brace k}$, the ordinary Stirling number of the second kind.

Explicit expressions for, and identities satisfied by, the $S_w(k)$ have been
obtained by numerous authors, and combinatorial interpretations have been
presented. Here we provide a new combinatorial interpretation that retains the
spirit of the familiar interpretation of ${n \brace k}$ as a count of
partitions. Specifically, we associate to each $w$ a graph $G_w$, and we show
that $S_w(k)$ enumerates partitions of the vertex set of $G_w$ into classes
that do not span an edge of $G_w$. We also discuss some relatives of, and
consequences of, our interpretation. 2013/08/14 - 10:07

We study the properties of affine rigidity of a hypergraph and prove a
variety of fundamental results. First, we show that affine rigidity is a
generic property (i.e., depends only on the hypergraph, not the particular
embedding). Then we prove that a graph is generically neighborhood affinely
rigid in d-dimensional space if it is (d+1)-vertex-connected. We also show
neighborhood affine rigidity of a graph implies universal rigidity of its
squared graph. Our results, and affine rigidity more generally, have natural
applications in point registration and localization, as well as connections to
manifold learning. 2013/08/14 - 10:07

An important property of the Kalman filter is that the underlying Riccati
flow is a contraction for the natural metric of the cone of symmetric positive
definite matrices. The present paper studies the geometry of a low-rank version
of the Kalman filter. The underlying Riccati flow evolves on the manifold of
fixed rank symmetric positive semidefinite matrices. Contraction properties of
the low-rank flow are studied by means of a suitable metric recently introduced
by the authors. 2013/08/14 - 10:07

In this paper, we study the problem of learning from weakly labeled data,
where labels of the training examples are incomplete. This includes, for
example, (i) semi-supervised learning where labels are partially known; (ii)
multi-instance learning where labels are implicitly known; and (iii) clustering
where labels are completely unknown. Unlike supervised learning, learning with
weak labels involves a difficult Mixed-Integer Programming (MIP) problem.
Therefore, it can suffer from poor scalability and may also get stuck in local
minimum. In this paper, we focus on SVMs and propose the WellSVM via a novel
label generation strategy. This leads to a convex relaxation of the original
MIP, which is at least as tight as existing convex Semi-Definite Programming
(SDP) relaxations. Moreover, the WellSVM can be solved via a sequence of SVM
subproblems that are much more scalable than previous convex SDP relaxations.
Experiments on three weakly labeled learning tasks, namely, (i) semi-supervised
learning; (ii) multi-instance learning for locating regions of interest in
content-based information retrieval; and (iii) clustering, clearly demonstrate
improved performance, and WellSVM is also readily applicable on large data
sets. 2013/08/14 - 10:07

We introduce GP-FNARX: a new model for nonlinear system identification based
on a nonlinear autoregressive exogenous model (NARX) with filtered regressors
(F) where the nonlinear regression problem is tackled using sparse Gaussian
processes (GP). We integrate data pre-processing with system identification
into a fully automated procedure that goes from raw data to an identified
model. Both pre-processing parameters and GP hyper-parameters are tuned by
maximizing the marginal likelihood of the probabilistic model. We obtain a
Bayesian model of the system's dynamics which is able to report its uncertainty
in regions where the data is scarce. The automated approach, the modeling of
uncertainty and its relatively low computational cost make of GP-FNARX a good
candidate for applications in robotics and adaptive control. 2013/08/14 - 10:07