73 citations · 785 across the 86 of their papers we have counts for
12 papers · 1 filter
Approximating pathwidth for graphs of small treewidth
Carla Groenland, Gwenaël Joret, Wojciech Nadara +1
We describe a polynomial-time algorithm which, given a graph with treewidth , approximates the pathwidth of to within a ratio of . This is the first a…
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…
Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments
Gerardo Berbeglia, Gwenaël Joret
The assortment problem in revenue management is the problem of deciding which subset of products to offer to consumers in order to maximise revenue. A simple and natural strategy i…
Reducing the rank of a matroid
Gwenaël Joret, Adrian Vetta
We consider the rank reduction problem for matroids: Given a matroid M and an integer k, find a minimum size subset of elements of M whose removal reduces the rank of M by at least…
Hitting and Harvesting Pumpkins
Gwenaël Joret, Christophe Paul, Ignasi Sau +2
The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a conn…
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…