Sorting under Partial Information (without the Ellipsoid Algorithm) (2009)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël, Jungers, Raphaël, Munro, J. Ian
We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and...
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs (2009)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Newman, Ilan, Weimann, Oren
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS'07. The game is played on a graph (representing a network), whose edges are colored either...
Detecting all regular polygons in a point set (2009)
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Iacono, John, Langerman, Stefan
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our...
Abstract Region Counting Circles (2009)
Jean Cardinal, Sébastien Collette, Stefan Langerman
The region counting distances, introduced by Demaine, Iacono and Langerman [5], associate to any pair of points p, q the number of items of a dataset S contained in a region R(p, q) surrounding p, q....
Abstract Region Counting Graphs (2009)
Jean Cardinal, Sébastien Collette, Stefan Langerman
A new family of proximity graphs, called region counting graphs (RCG) is presented. The RCG for a finite set of points in the plane uses the notion of region counting distance introduced by Demaine...
Abstract Pricing of Geometric Transportation Networks (2008)
Jean Cardinal, Martine Labbé, Stefan Langerman, Belén Palop
We propose algorithms for pricing a transportation network in such a way that the profit generated by the customers is maximized. We model the transportation network as a subset of the plane and take...
An Efficient Algorithm for Partial Order Production (2008)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël, Jungers, Raphaël M., Munro, J. Ian
We consider the problem of partial order production: arrange the elements of an unknown totally ordered T into a target partially ordered set S, by comparing a minimum number of pairs in T. Special...
Where to build a temple, and where to dig to find one (2008)
Greg Aloupis, Jean Cardinal, Sébastien Collette, John Iacono, Stefan Langerman
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We use two different approaches to find regular polygons, depending on their number of edges. Those...
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Hurtado, Ferran, Langerman, Stefan, O'Rourke, Joseph, ...
A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of...
Optimal Location of Transportation Devices (2008)
Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Belén Palop
Abstract. We consider algorithms for finding the optimal location of a simple transportation device, that we call a moving walkway, consisting of a pair of points in the plane between which the...
Noname manuscript No. (will be inserted by the editor) (2008)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
the date of receipt and acceptance should be inserted later Abstract We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy...
Noname manuscript No. (will be inserted by the editor) (2008)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
the date of receipt and acceptance should be inserted later Abstract We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy...
S.: Designing small keyboards is hard (2008)
Jean Cardinal, Stefan Langerman
Abstract. We study the problem of placing symbols of an alphabet onto the minimum number of keys on a small keyboard so that any word of a given dictionary can be recognized univoquely only by...
Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman
Abstract. We analyze a new popular video-game called Lumines, which was developed by Sony for the PSP platform. It involves a sequence of bichromatic 2x2 blocks that fall in a grid and must be...
Improved Approximation Bounds for Edge Dominating Set in Dense Graphs (2008)
Jean Cardinal, Stefan Langerman, Eythan Levy
Abstract. We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints....
Selfish Service Installation in Networks (Extended Abstract) (2008)
Abstract. We consider a scenario of distributed service installation in privately owned networks. Our model is a non-cooperative vertex cover game for k players. Each player owns a set of edges in a...
c ○ Fachbereich Mathematik und Statistik (2008)
Martin Röder, Jean Cardinal, Raouf Hamzaoui, Martin Röder, ...
On the complexity of rate-distortion optimal streaming
Abstract Region Counting Circles (2008)
Jean Cardinal, Sébastien Collette, Stefan Langerman
The region counting distances, introduced by Demaine, Iacono and Langerman [5], associate to any pair of points p, q the number of items of a dataset S contained in a region R(p, q) surrounding p, q....
Set Covering Problems with General Objective Functions (2008)
Cardinal, Jean, Dumeunier, Christophe
We introduce a parameterized version of set cover that generalizes several previously studied problems. Given a ground set V and a collection of subsets S_i of V, a feasible solution is a partition...
Minimum Entropy Orientations (2008)
Cardinal, Jean, Fiorini, Samuel, Joret, Gwenaël
We study graph orientations that minimize the entropy of the in-degree sequence. The problem of finding such an orientation is an interesting special case of the minimum entropy set cover problem...
Juggling with pattern matching (2008)
Jean Cardinal, Steve Kremer, Stefan Langerman
In the late eighties, it was shown that juggling patterns can be described by strings of numbers with fascinating combinatorial properties that have since then been studied by many mathematicians and...
Abstract Pricing of Geometric Transportation Networks (2008)
Jean Cardinal, Martine Labbé, Stefan Langerman, Belén Palop
We propose algorithms for pricing a transportation network in such a way that the profit generated by the customers is maximized. We model the transportation network as a subset of the plane and take...
Improved Approximation Bounds for Edge Dominating Set in Dense Graphs (2008)
Jean Cardinal, Stefan Langerman, Eythan Levy
Abstract. We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints....
Juggling with Pattern Matching (2008)
Jean Cardinal, Steve Kremer, Stefan Langerman
In the late eighties, it was shown that juggling patterns can be described by strings of numbers with fascinating combinatorial properties that have since then been studied by many mathematicians and...
Minimum Sum Edge Colorings of Multicycles (2008)
Cardinal, Jean, Ravelomanana, Vlady, Valencia-Pabon, Mario
In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is...
Minimum Sum Edge Colorings of Multicycles (2008)
Cardinal, Jean, Ravelomanana, Vlady, Valencia-Pabon, Mario
In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is...
Fast Entropy-Constrained Vector Quantizer Design (2007)
Vector quantization is the process of encoding vector data as an index to a dictionary -- or codebook -- of representative vectors. Entropy-constrained vector quantizers (ECVQ) explicitly control the...
Faster Fractal Image Coding Using Similarity Search in a KL-transformed Feature Space (2007)
Jean Cardinal Brussels, Jean Cardinal
. Fractal coding is an efficient method of image compression but has a major drawback: the very slow compression phase, due to a time-consuming similarity search between image blocks. A general...
Assche, “On minimum entropy graph colorings (2007)
Jean Cardinal, Samuel Fiorini, Gilles Van Assche
Abstract--- We study properties of graph colorings that minimize the quantity of color information with respect to a given probability distribution on the vertices. The minimum entropy of any...
Jean Cardinal, Ludo Tolhuizen, Agnieszka Miguel, Alex Mohr, Henrique Malvar, Mike Fleming
These presentee en vue de l'obtention du grade de Docteur en Sciences
Faster Fractal Image Coding Using Similarity Search in a KL-transformed Feature Space (2007)
Abstract. Fractal coding is an efficient method of image compression but has a major drawback: the very slow compression phase, due to a time-consuming similarity search between image blocks. A...
Quantization with an Information-Theoretic Distortion Measure (2007)
We consider the following problem: given two nonindependent random variables, nd a quantizer for the rst variable such that the mutual information between the quantizer output and the second variable...
Designing Small Keyboards is Hard (2007)
Jean Cardinal, Stefan Langerman
We study the problem of placing symbols of an alphabet onto the minimum number of keys on a small keyboard so that any word of a given dictionary can be recognized univoquely only by looking at the...
Juggling with Pattern Matching (2007)
Jean Cardinal, Steve Kremer, Stefan Langerman
In the late eighties, it was shown that juggling patterns can be described by strings of numbers with fascinating combinatorial properties that have since then been studied by many mathematicians and...
Chromatic Edge Strength of Some Multigraphs (2007)
Cardinal, Jean, Ravelomanana, Vlady, Valencia-Pabon, Mario
The edge strength $s'(G)$ of a multigraph $G$ is the minimum number of colors in a minimum sum edge coloring of $G$. We give closed formulas for the edge strength of bipartite multigraphs and...
Minimum Sum Edge Colorings of Multicycles (2007)
Cardinal, Jean, Ravelomanana, Vlady, Valencia-Pabon, Mario
In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is...
The Stackelberg Minimum Spanning Tree Game (2007)
Cardinal, Jean, Demaine, Erik D., Fiorini, Samuel, Joret, Gwenaël, Langerman, Stefan, Newman, Ilan, ...
We consider a one-round two-player network pricing game, the {\em Stackelberg Minimum Spanning Tree} game or StackMST. The game is played on a graph (representing a network), whose edges are colored...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Stefan Langerman, Ilan Newman, Oren Weimann
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
The Stackelberg Minimum Spanning Tree Game (2007)
Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, ...
Abstract. We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are...
Tight results on minimum entropy set cover (2006)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set...
Tight results on minimum entropy set cover (2006)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
Abstract. In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the...
Tight results on minimum entropy set cover (2006)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set...
A tight analysis of the maximal matching heuristic (2005)
Jean Cardinal, Martine Labbé, Stefan Langerman, Eythan Levy, Hadrien Mélot
We study the worst-case performance of the maximal matching heuristic applied to the Minimum Vertex Cover and Minimum Maximal Matching problems, through a careful analysis of tight examples. We show...
A tight analysis of the maximal matching heuristic (2005)
Jean Cardinal, Martine Labbé, Stefan Langerman, Eythan Levy
Abstract. We study the algorithm that iteratively removes adjacent vertices from a simple, undirected graph until no edge remains. This algorithm is a well-known 2-approximation to three classical...
Entropy-constrained index assignments for multiple description quantizers (2004)
Abstract. Multiple description coding has revealed itself highly useful for the transmission of digital signals over packet-switched networks or diversity systems. The index assignment problem is...
On the Complexity of Rate-Distortion Optimal Streaming of Packetized Media (2004)
Fachbereich Informatik Und Informationswissenschaft, Martin Röder, Martin Roder, Raouf Hamzaoui, Raouf Hamzaoui, Raouf Hamzaoui, ...
We consider the problem of optimal rate-distortion streaming of packetized multimedia data in the context of sender-driven transmission over a single-QoS network using feedback and retransmissions....
A Graph Coloring Problem with Applications to Data Compression (2004)
Jean Cardinal, Samuel Fiorini, Gilles Van Assche
We study properties of graph colorings that minimize the quantity of color information with respect to a given probability distribution P on the vertices of the graph. The minimum entropy of any...
Local properties of geometric graphs (2004)
Jean Cardinal, Sébastien Collette, Stefan Langerman
We propose a definition of locality for properties of geometric graphs. We measure the local density of graphs using region-counting distances [8] between pairs of vertices, and we use this density...
A Graph Coloring Problem with Applications to Data Compression (2004)
Jean Cardinal, Samuel Fiorini, Gilles Van Assche
We study properties of graph colorings that minimize the quantity of color information with respect to a given probability distribution P on the vertices of the graph. The minimum entropy of any...
Lazy algorithms for dynamic closest pair with arbitrary distance measures (2003)
Abstract. We propose novel lazy algorithms for the dynamic closest pair problem with arbitrary distance measures. They use a simple delayed computation mechanism to spare distance calculations. One...
Assche. Construction of a shared secret key using continuous variables (2003)
Jean Cardinal, Gilles Van Assche
Abstract--- Motivated by recent advances in quantum cryptography with continuous variables, we study the problem of extracting a shared digital secret key from two correlated real values. Alice has...
Multistage index assignments for M-description coding (2003)
We consider the problem of generalized multiple description coding of image data, in which an image is encoded into M descriptions sent over M unreliable channels, and any description subset is...
Compression of side information (2003)
We consider the problem of data compression with side information at the decoder and propose novel algorithms for quantization of the side information. These methods build quantizers that minimize...
Construction of a Shared Secret Key Using Continuous Variables (2003)
Jean Cardinal, Gilles Van Assche
Motivated by recent advances in quantum cryptography with continuous variables, we study the problem of extracting a shared digital secret key from two correlated real values. Alice has access to a...
ITW2003, Paris, France, March 31 -- April 4, 2003 (2003)
Construction Of Shared, Jean Cardinal, Gilles Van Assche
Motivated by recent advances in quantum cryptography with continuous variables, we study the problem of extracting a shared digital secret key from two correlated real values. Alice has access to a...
Troyanov, Stéphan, Cardinal, Jean, Geadah, David, Parent, Daniel, Courteau, Sylvie, Caron, Sylvie, ...
Troyanov, Stéphan, Cardinal, Jean, Geadah, David, Parent, Daniel, Courteau, Sylvie, Caron, Sylvie, ...
Background. In continuous venovenous haemofiltration (CVVH), high ultrafiltration rates provide survival benefits in acute renal failure. This study measured clearances obtained at...
Asche, “Joint entropy-constrained multiterminal quantization (2002)
Jean Cardinal, Gilles Van Assche
Abstract | We study the design of entropy-constrained multiterminal quantizers for coding two correlated continuous sources. Two design algorithms are presented, both optimizing a Lagrangian cost...
Joint Entropy-Constrained Multiterminal Quantization (2002)
Jean Cardinal, Gilles Van Assche
We study the design of entropy-constrained multiterminal quantizers for coding two correlated continuous sources. Two design algorithms are presented, both optimizing a Lagrangian cost measure...
Multipath Tree-Structured Vector Quantizers (2000)
Tree-structured vector quantization (TSVQ) is a popular mean of avoiding the exponential complexity of fullsearch vector quantizers. We present two new design algorithms for TSVQ in which more than...
Fast Search Techniques for Product Code Vector Quantizers (1999)
Vector quantization is an efficient compression technique for which many variants are known. Product code vector quantizers use multiple codebooks for coding separately features of a vector. In...
Fractal Compression Using the Discrete Karhunen-Loeve Transform (1998)
. Fractal coding of images is a quite recent and efficient method whose major drawback is the very slow compression phase, due to a timeconsuming similarity search between image blocks. A general...