15 citations · 42 across the 16 of their papers we have counts for
4 papers · 1 filter
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs
Joseph Cheriyan, Laszlo A. Vegh
We present a 6-approximation algorithm for the minimum-cost -node connected spanning subgraph problem, assuming that the number of nodes is at least . We apply a com…
Oriented Euler Complexes and Signed Perfect Matchings
László A. Végh, Bernhard von Stengel
This paper presents "oriented pivoting systems" as an abstract framework for complementary pivoting. It gives a unified simple proof that the endpoints of complementary pivoting pa…
The Cutting Plane Method is Polynomial for Perfect Matchings
Karthekeyan Chandrasekaran, Laszlo A. Vegh, Santosh Vempala
The cutting plane approach to optimal matchings has been discussed by several authors over the past decades (e.g., Padberg and Rao '82, Grotschel and Holland '85, Lovasz and Plumme…
LP-based Covering Games with Low Price of Anarchy
Georgios Piliouras, Tomas Valla, Laszlo A. Vegh
We present a new class of vertex cover and set cover games. The price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimizati…