Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem

Nader H. Bshouty, Lynn Burroughs

Type: Book-Chapter

Publication Date: 1998-01-01

Citations: 77

DOI: https://doi.org/10.1007/bfb0028569

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	Parameterized Approximation via Fidelity Preserving Transformations	2012	Michael R. Fellows Ariel Kulik Frances Rosamond Hadas Shachnai
+	Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs	2017	Sam Chiu-wai Wong
+	A faster algorithm for Vertex Cover parameterized by solution size	2022	David G. Harris N. S. Narayanaswamy
+	Maximization Problems Parameterized Using Their Minimization Versions: The Case of Vertex Cover	2015	Meirav Zehavi
+	Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs	2016	Sam Chiu-wai Wong
+	Maximization Problems Parameterized Using Their Minimization Versions: The Case of Vertex Cover.	2015	Meirav Zehavi
+	An improved fixed parameter tractable algorithm for vertex cover	1999	Ulrike Stege Michael R. Fellows
+	On the approximability of the vertex cover and related problems	2007	Qiaoming Han Abraham P. Punnen
+	Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes	2018	Arash Haddadan Alantha Newman
+	LP-based Covering Games with Low Price of Anarchy	2012	Georgios Piliouras Tomáš Valla László A. Végh
+	LP-based Covering Games with Low Price of Anarchy	2012	Georgios Piliouras Tomas Valla László A. Végh
+	The Primal-Dual Greedy Algorithm for Weighted Covering Problems	2017	Britta Peis José Verschae Andreas Wierz
+ PDF Chat	Approximating Sparse Covering Integer Programs Online	2014	Anupam Gupta Viswanath Nagarajan
+	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover	2020	Nikhil Bansal Jatin Batra Majid Farhadi Prasad Tetali
+	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover	2020	Nikhil Bansal Jatin Batra Majid Farhadi Prasad Tetali
+ PDF Chat	A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads	2024	Benjamin Rockel-Wolff
+	No Small Linear Program Approximates Vertex Cover within a Factor $2 - ε$	2015	Abbas Bazzi Samuel Fiorini Sebastian Pokutta Ola Svensson
+	Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems	2020	Chandra Chekuri Kent Quanrud Manuel R. Torres
+ PDF Chat	Knapsack with Vertex Cover, Set Cover, and Hitting Set	2024	Palash Dey Ashlesha Hota Sudeshna Kolay Sipra Singh
+	No Small Linear Program Approximates Vertex Cover within a Factor 2 -- e	2015	Abbas Bazzi Samuel Fiorini Sebastian Pokutta Ola Svensson

Works That Cite This (14)

Action	Title	Year	Authors
+	On Partial Vertex Cover on Bipartite Graphs and Trees	2013	Bugra Caskurlu K. Subramani
+	The Local Ratio Technique and Its Application to Scheduling and Resource Allocation Problems	2005	Reuven Bar-Yehuda Keren Bendel Ari Freund Dror Rawitz
+	Using homogenous weights for approximating the partial cover problem	1999	Reuven Bar-Yehuda
+	Lift & project systems performing on the partial-vertex-cover polytope	2020	Konstantinos Georgiou Andy Jiang Edward Lee Astrid A. Olave Ian Seong Twesh Upadhyaya
+	Maximum weighted independent sets with a budget	2015	Tushar Kalra Rogers Mathew Sudebkumar Prasant Pal Vijay Kumar Pandey
+	Lift & Project Systems Performing on the Partial-Vertex-Cover Polytope	2014	Κωνσταντίνος Γεωργίου Andy Jiang Edward Lee Astrid A. Olave Ian Seong Twesh Upadhyaya
+	On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs	2022	Vahan Mkrtchyan Garik Petrosyan
+ PDF Chat	Algorithms for covering multiple submodular constraints and applications	2022	Chandra Chekuri Tanmay Inamdar Kent Quanrud Kasturi Varadarajan Zhao Zhang
+ PDF Chat	Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems	2013	Samir Khuller Manish Purohit Kanthi Sarpatwar
+	On the Partition Set Cover Problem	2018	Tanmay Inamdar Kasturi Varadarajan

Works Cited by This (2)

Action	Title	Year	Authors
+	The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover	1998	Jon Kleinberg Michel X. Goemans
+ PDF Chat	Approximate graph coloring by semidefinite programming	2002	David R. Karger R. Motwani Madhu Sudan