Time filter

Source Type

Chepoi V.,CNRS Laboratory of Fundamental Informatics of Marseille (LIF) | Felsner S.,TU Berlin
Computational Geometry: Theory and Applications | Year: 2013

In this note, we present a simple combinatorial factor 6 algorithm for approximating the minimum hitting set of a family R={R1,⋯, Rn} of axis-parallel rectangles in the plane such that there exists an axis-monotone curve γ that intersects each rectangle in the family. The quality of the hitting set is shown by comparing it to the size of a packing (set of pairwise non-intersecting rectangles) that is constructed along, hence, we also obtain a factor 6 approximation for the maximum packing of R. In cases where the axis-monotone curve γ intersects the same side (e.g. the bottom side) of each rectangle in the family the approximation factor for hitting set and packing is 3. © 2013 Elsevier B.V. Source

Kaced T.,CNRS Laboratory of Fundamental Informatics of Marseille (LIF)
IEEE International Symposium on Information Theory - Proceedings | Year: 2011

To split a secret s between several participants, we generate (for each value of s) shares for all participants. The goal: authorized groups of participants should be able to reconstruct the secret but forbidden ones get no information about it. We introduce several notions of non-perfect secret sharing, where some small information leak is permitted. We study its relation to the Kolmogorov complexity version of secret sharing (establishing some connection in both directions) and the effects of changing the secret size (showing that we can decrease the size of the secret and the information leak at the same time). © 2011 IEEE. Source

Delacourt M.,CNRS Laboratory of Fundamental Informatics of Marseille (LIF)
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011

Cellular automata are a parallel and synchronous computing model, made of infinitely many finite automata updating according to the same local rule. Rice's theorem states that any nontrivial property over computable functions is undecidable. It has been adapted by Kari to limit sets of cellular automata [7], that is the set of configurations that can be reached arbitrarily late. This paper proves a new Rice theorem for μ-limit sets, which are sets of configurations often reached arbitrarily late. © 2011 Springer-Verlag. Source

Saxena A.,Axioma Inc | Bonami P.,CNRS Laboratory of Fundamental Informatics of Marseille (LIF) | Lee J.,IBM
Mathematical Programming | Year: 2010

This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non- convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities from the equation Y = x x T . We use the non-convex constraint Y - x xT 0 to derive disjunctions of two types. The first ones are directly derived from the eigenvectors of the matrix Y - x x T with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the width of the disjunction. We also use the convex SDP constraint Y - x xT 0 to derive convex quadratic cuts, and we combine both approaches in a cutting plane algorithm. We present computational results to illustrate our findings. © 2010 Springer and Mathematical Programming Society. Source

Baudru N.,CNRS Laboratory of Fundamental Informatics of Marseille (LIF)
Theoretical Computer Science | Year: 2011

Asynchronous automata are a model of communication processes with a control structure distributed on a set P of processes, global initializations and global accepting conditions. The well-known theorem of Zielonka states that they recognize exactly the class of regular Mazurkiewicz trace languages. The corresponding synthesis problem is, given a global specification A of any regular trace language L, to build an asynchronous automaton that recognizes L, automatically. Yet, all such existing constructions are quite involved and yield an explosion of the number of states in each process, which is exponential in both the sizes of A and P. In this paper, we introduce the particular case of distributed asynchronous automata, which require that the initializations and the accepting conditions are distributed as well. We present an original technique based on simple compositions/decompositions of these distributed asynchronous automata that results in the construction of smaller non-deterministic asynchronous automata: now, the number of states in each process is only polynomial in the size of A, but is still exponential in the size of P. © 2011 Elsevier B.V. All rights reserved. Source

Discover hidden collaborations