81 citations · 388 across the 46 of their papers we have counts for
8 papers · 1 filter
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
Karthekeyan Chandrasekaran, Chandra Chekuri, Samuel Fiorini +2
We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph with non-negative vertex costs. The goal is to find a mini…
Improved approximation algorithms for hitting 3-vertex paths
Samuel Fiorini, Gwenaël Joret, Oliver Schaudt
We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. Thi…
Approximating the Balanced Minimum Evolution Problem
Samuel Fiorini, Gwenaël Joret
We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instan…
Minimum Entropy Combinatorial Optimization Problems
Jean Cardinal, Samuel Fiorini, Gwenaël Joret
We survey recent results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution. These include the minimum entropy set cov…
Hitting Diamonds and Growing Cacti
Samuel Fiorini, Gwenaël Joret, Ugo Pietropaoli
We consider the following NP-hard 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. We obtain a c…
Sorting under Partial Information (without the Ellipsoid Algorithm)
Jean Cardinal, Samuel Fiorini, Gwenaël Joret +2
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…