Hitting Diamonds and Growing Cacti (2009)
Fiorini, Samuel, Joret, Gwenaël, Pietropaoli, Ugo
We consider the following problem: in a weighted graph, find a minimum cost set of vertices whose removal leaves a graph in which no two cycles share an edge. This NP-hard problem belongs to a...
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...
A closest vector problem arising in radiation therapy planning (2009)
Engelbeen, Celine, Fiorini, Samuel, Kiesel, Antje
In this paper we consider the problem of finding a vector that can be written as a nonnegative, integer and linear combination of given 0-1 vectors, the generators, such that the l_1-distance between...
The Virtual Private Network Design Problem with Concave Costs (Oberwolfach abstract) (2008)
Fiorini, Samuel, Oriolo, Gianpaolo, Sanità, Laura, Theis, Dirk Oliver
The symmetric Virtual Private Network Design (VPND) problem is concerned with buying capacity on links (edges) in a communication network such that certain traffic demands can be met. We investigate...
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...
Doignon, Jean-Paul, Fiorini, Samuel, Joret, Gwenaël
A graph is alpha-critical if its stability number increases whenever an edge is removed from its edge set. The class of alpha-critical graphs has several nice structural properties, most of them...
AND THE LINEAR ORDERING PROBLEM: 2 SURFACES THAT DEFINE FACETS (2008)
Abstract. We find new facet-defining inequalities for the linear ordering polytope generalizing the well-known Möbius ladder inequalities. Our starting point is to observe that the natural...
Journal of Integer Sequences, Vol. 6 (2003), Article 03.4.3 Counting Biorders (2008)
Julie Christophe, Jean-paul Doignon, Samuel Fiorini, Département De Mathématique
Biorders were introduced first as Guttman scales and then as Ferrers relations. They are now well recognized in combinatorics and its applications. However, it seems that no procedure besides plain...
Jean-paul Doignon, Samuel Fiorini, Gwenaël Joret
A graph is α-critical if its stability number increases whenever an edge is removed from its edge set. The class of α-critical graphs has several nice structural properties, most of them related to...
A NOTE ON THE PRECEDENCE-CONSTRAINED CLASS SEQUENCING PROBLEM (2008)
José R. Correa, Samuel Fiorini, Nicolás Stier-moses
Abstract. We give a short proof of a result of Tovey [5] on the inapproximability of a scheduling problem known as precedence constrained class sequencing. In addition we present an approximation...
Approximate Min-Max Relations for Odd (2008)
Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta
Abstract We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio...
A Note on a Theorem of Sewell and Trotter (2008)
Abstract. Sewell and Trotter proved that every connected α-critical graph that is not isomorphic to K1, K2 or an odd cycle contains a totally odd K4-subdivision. Their theorem implies an interesting...
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...
The Polyhedron of all Representations of a (2008)
Barry Balof, Jean-paul Doignon, Samuel Fiorini
In many practical situations, indifference is intransitive. This led Luce (1956) to base a preference model on the following principle: an alternative is judged better than another one only if the...
A NOTE ON THE PRECEDENCE-CONSTRAINED CLASS SEQUENCING PROBLEM (2008)
José R. Correa, Samuel Fiorini, E. Stier-moses
Abstract. We give a short proof of a result of Tovey [6] on the inapproximability of a scheduling problem known as precedence constrained class sequencing. In addition, we present an approximation...
A little note on the Cops & Robber game on graphs embedded in non-orientable surfaces (2008)
Clarke, Nancy E., Fiorini, Samuel, Joret, Gwenaël, Theis, Dirk Oliver
The two-player, complete information game of Cops and Robber is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges....
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...
On a Theorem of Sewell and Trotter (2007)
Fiorini, Samuel, Joret, Gwenaël
Sewell and Trotter [J. Combin. Theory Ser. B, 1993] proved that every connected alpha-critical graph that is not isomorphic to K_1, K_2 or an odd cycle contains a totally odd K_4-subdivision. Their...
Facets Of The Weak Order Polytope Derived From The Induced Partition Projection (2007)
Jean-paul Doignon, Samuel Fiorini
. The weak order polytopes are studied in Gurgel and Wakabayashi (1997), Gurgel and Wakabayashi (1996), and Fiorini and Fishburn (1999). We make use of their natural, affine projection onto the...
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...
The VPN Tree Routing Conjecture for Outerplanar Networks (2007)
Fiorini, Samuel, Oriolo, Gianpaolo, Sanità, Laura, Theis, Dirk Oliver
The VPN Tree Routing Conjecture is a conjecture about the Virtual Private Network Design problem. It states that the symmetric version of the problem always has an optimum solution which has a...
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...
Céline Engelbeen, Samuel Fiorini
We consider combinatorial optimization problems arising in radiation therapy. Given a matrix I with non-negative integer entries, we seek for a decomposition of I as a weighted sum of binary matrices...
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...
The approval-voting polytope: combinatorial interpretation of the facets (2006)
Doignon, Jean-paul;, Fiorini, Samuel
Doignon et Fiorini (2003) déterminent toutes les facettes du polytope du vote approbatoire. Ils livrent ainsi une caractérisation d'un modèle probabiliste dû à Falmagne et Regenwetter (1996) :...
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...
Planar graph bipartization in linear time (2005)
Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta
Abstract. For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of...
A Note on the Precedence-Constrained Class Sequencing Problem (2004)
Jose R. Correa, Samuel Fiorini, Nicolas Stier-Moses
We give a short proof of a result of Tovey [5] on the inapproximability of a scheduling problem known as precedence constrained class sequencing. In addition we present an approximation algorithm...
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...
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...
The approval-voting polytope: combinatorial interpretation of the facets (2003)
Jean-paul Doignon, Samuel Fiorini
Doignon et Fiorini (2003) déterminent toutes les facettes du polytope du vote approbatoire. Ils livrent ainsi une caractérisation d'un modèle probabiliste dû à Falmagne et Regenwetter (1996) :...
Determining the Automorphism Group of the Linear Ordering Polytope (1999)
In this paper we explore the combinatorial automorphism group of the linear ordering polytope P n LO for each n ? 1. We establish that this group is isomorphic to Z 2 \Theta Sym(n + 1) if n ? 2 (and...
Samuel Fiorini, Peter Fishburn
imary: 52B12, 52B15; secondary: 90A06, 90A08. OR/MS Index 1978 subject classification. Primary: Decision Theory, Programming. Key words. Weak order, partition, polytope, preference, choice...
Julie Christophe, Jean-paul Doignon, Samuel Fiorini
Biorders were introduced rst as Guttman scales and then as Ferrers relations. They are now well recognized in combinatorics and its applications. However, it seems that no procedure besides plain...