120,434 research outputs found
Quantifying the Discord: Order Discrepancies in Message Sequence Charts
No full textMessage Sequence Charts (MSCs) and High-level Message Sequence Charts (HMSC) are formalisms used to describe scenarios of message passing protocols. We propose using Allen's logic to study the temporal order of the messages. We introduce the concept of {\em discord} to quantify the order discrepancies between messages in different nodes of an HMSC and study its algorithmic properties. We show that while discord of a pair of messages is hard to compute in general, the problem becomes polynomial-time computable if the number of nodes of the HMSC or the number of processes is constant. Moreover, for a given HMSC, it is always computationally easy to identify a pair of messages that exhibits the worst-case discord, and compute the discord of this pair
A Note on Stabbing Convex Bodies with Points, Lines, and Flats
Full text linkConsider the
problem of constructing weak \eps-nets where the stabbing elements are lines
or -flats instead of points. We study this problem in the simplest setting
where it is still interesting -- namely, the uniform measure of volume over the
hypercube . Specifically, a (k,\eps)-net is a set of
-flats, such that any convex body in of volume larger than \eps
is stabbed by one of these -flats. We show that for , one can
construct (k,\eps)-nets of size O(1/\eps^{1-k/d}). We also prove that any
such net must have size at least \Omega(1/\eps^{1-k/d}). As a concrete
example, in three dimensions all \eps-heavy bodies in can be
stabbed by \Theta(1/\eps^{2/3}) lines. Note, that these bounds are
\emph{sublinear} in 1/\eps, and are thus somewhat surprising. The new
construction also works for points providing a weak \eps-net of size
O(\tfrac{1}{\eps}\log^{d-1} \tfrac{1}{\eps} ).Comment: 13 pages, 6 figures; updated with improved constructions of -nets for $k \geq 1
Transition Systems with Independence and Multi-Arcs
No full textWe extend the model of transition systems with independence in order to provide it with a feature relevant in the noninterleaving analysis of concurrent systems, namely multi-arcs. Moreover, we study the relationships between the category of transition systems with independence and multi-arcs and the category of labeled asynchronous transition systems, extending the results recently obtained by the authors for (simple) transition systems with independence (cf. Proc. CONCUR'96), and yielding a precise characterisation of transition systems with independence and multi-arcs in terms of (event-maximal, diamond-extensional) labeled asynchronous transition systems
A nested depth first search algorithm for model checking with symmetry reduction
No full textWe present an algorithm for the verification of properties of distributed systems, represented as Büchi automata, which exploits symmetry reduction. The algorithm is developed in the more general context of bisimulation preserving reductions along the lines of Emerson, Jha and Peled. Our algorithm is a modification of the nested depth first search (NDFS) algorithm by Courcoubetis, Yannakakis, Vardi and Wolper. As such, it has the standard advantages (memory and time efficiency) that NDFS shows over the state space exploration algorithms based on maximal strongly connected components in the state space graph. In addition, a nice feature of the presented algorithm is that it works also with multiple (non-canonical) representatives for the symmetry equivalence classes. Also, instead of an abstract counter-example, our algorithm is capable of reproducing a counter-example which exists in the original unreduced state space, which is an important feature for debugging
Journey to the Center of the Point Set
Full text linkWe revisit an algorithm of Clarkson et al. [K. L. Clarkson et al., 1996], that computes (roughly) a 1/(4d^2)-centerpoint in O~(d^9) time, for a point set in R^d, where O~ hides polylogarithmic terms. We present an improved algorithm that computes (roughly) a 1/d^2-centerpoint with running time O~(d^7). While the improvements are (arguably) mild, it is the first progress on this well known problem in over twenty years. The new algorithm is simpler, and the running time bound follows by a simple random walk argument, which we believe to be of independent interest. We also present several new applications of the improved centerpoint algorithm
Improved Approximation Algorithms for Tverberg Partitions
Full text link
Tverberg's theorem states that a set of points in can be
partitioned into \floor{n/(d+1)} sets with a common intersection. A point in
this intersection (aka Tverberg point) is a centerpoint of the input point set,
and the Tverberg partition provides a compact proof of this, which is
algorithmically useful.
Unfortunately, computing a Tverberg point exactly requires time.
We provide several new approximation algorithms for this problem, which improve
either the running time or quality of approximation, or both. In particular, we
provide the first strongly polynomial (in both and ) approximation
algorithm for finding a Tverberg point
Capital Accumulation and Annuities in an Adverse Selection Economy
Full text linkThis paper suggests that adverse selection problems in competitive annuity markets can generate quantity constrained equilibria in which some agents whose length of lifetime is uncertain find it advantageous to accumulate capital privately. This occurs despite the higher rates of return on annuities. The welfare properties of these allocations are analyzed. It is shown that the level of capital accumulation is excessive in a Paretian sense. Policies which eliminate this inefficiency are discussed.
Fast Algorithms for Geometric Consensuses
Full text linkLet P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P.
We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others
Robust Proximity Search for Balls Using Sublinear Space
Full text linkGiven a set of n disjoint balls b_1, ..., b_n in R^d, we provide a data structure, of near linear size, that can answer (1 +- epsilon)-approximate k-th-nearest neighbor queries in O(log(n) + 1/epsilon^d) time, where k and epsilon are provided at query time. If k and epsilon are provided in advance, we provide a data structure to answer such queries, that requires (roughly) O(n/k) space; that is, the data structure has sublinear space requirement if k is sufficiently large
- …
