Operations Research Seminar
— 2:30pm
Location:
In Person
-
Tepper 4242
Speaker:
CHANDRA CHEKURI
,
Paul and Cynthia Saylor Professor, Algorithms / Theory Group, Department of Computer Science, University of Illinois, Urbana-Champaign
http://chekuri.cs.illinois.edu/
Polyhedral Formulations for (Subset) Feedback Vertex Set
We consider feedback vertex set (FVS) in undirected graphs, and its generalization the subset feedback vertex set (SFVS) problem. In FVS the input is a vertex-weighted graph G=(V,E) and the goal is to remove a minimum weight susbet of vertices S such that the G-S has no cycles. In SFVS we are also given a subset T of the vertices called terminals, and the goal is to remove a minimum weight subset of vertices S such that G-S has no cycle containing a terminal. FVS is a well-known NP-Hard problem and admits a 2-approximation from several decades ago via the local-ratio method (Bafna et al, Becker and Geiger). Moreover 2 is the best approximation ratio one can hope for assuming the unique games conjecture. Chudak et al. developed an LP relaxation for FVS and interpreted the local-ratio algorithms as primal-dual algorithms with respect to this relaxation. However, their LP relaxation was not known to be solvable in polynomial time.
We develop a new LP relaxation that is poly-time solvable and has an integrality gap of 2. This LP relaxation is based on a connection to a relaxation for densest subgraph by Charikar. A few years ago Chekuri and Madan developed a poly-time solvable LP relaxation for the more general SFVS problem and they showed that it had an integrality gap of at most 13 via a rounding algorithm. They raised the question of whether their LP relaxation had an integrality gap of at most 2 for FVS (and also SFVS). We answer this question in the affirmative for FVS. Despite proving that these two LP relaxations (which come from different perspectives on the problem) have an integrality gap of at most 2 for FVS, we do not know a direct way to round the relaxations to achieve this bound. We conjecture an extreme point property for one of the LP relaxations that would allow one to obtain an iterated rounding 2-approximation algorithm, and provide evidence for this conjecture via a related result for the pseudo-forest deletion set problem.
The goal of the talk is to highlight the ideas and connections behind the several LP relaxations for these problems, and to point out several open problems.
Based on joint work with Karthik Chandrasekharan, Samuel Fiorini, Shubhang Kulkarni, and Stefan Weltge , and an older paper with Vivek Madan
—
Chandra Chekuri is the Paul and Cynthia Saylor Professor in the Department of Computer Science at University of Illinois, Urbana-Champaign. He joined the university in 2006 after spending eight years at Lucent Bell Labs. Prior to that he received his PhD from Stanford University and an undergraduate degree from IIT Chennai. He is interested in the design and analysis of algorithms, combinatorial optimization, and theoretical computer science. He is happy about some of his contributions to (fast) approximation algorithms, graphs and networks, scheduling, and optimizing with submodular functions.