13 Search Results for "Végh, László A."


Volume

LIPIcs, Volume 145

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA

Editors: Dimitris Achlioptas and László A. Végh

Document
Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization

Authors: Jakub Komárek and Martin Koutecký

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)


Abstract
Linear programming (LP) is a fundamental problem with rich theory and wide applications. A ubiquitous technique in LP is scaling, where the input instance is transformed in some way to make its solution easier. Dadush et al. [STOC '20] have recently devised an algorithm which scales the columns of the constraint matrix of a linear program in a way that aims to minimize the circuit imbalance measure, a matrix condition number of growing theoretical interest. They show that this rescaling achieves favorable theoretical guarantees for certain LP algorithms. We follow up on their work in an experimental manner. First, we have implemented their algorithm, overcoming several engineering obstacles. Next, we have used our implementation to obtain a rescaling of 142 publicly available instances. Finally, we have performed experiments evaluating the effects of the obtained rescalings on the runtime of real-world LP solvers, and we have evaluated their quality with regard to the circuit imbalance measure.

Cite as

Jakub Komárek and Martin Koutecký. Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{komarek_et_al:LIPIcs.SEA.2024.18,
  author =	{Kom\'{a}rek, Jakub and Kouteck\'{y}, Martin},
  title =	{{Experimental Analysis of LP Scaling Methods Based on Circuit Imbalance Minimization}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.18},
  URN =		{urn:nbn:de:0030-drops-203832},
  doi =		{10.4230/LIPIcs.SEA.2024.18},
  annote =	{Keywords: Linear programming, scaling, circuit imbalance measure}
}
Document
Track A: Algorithms, Complexity and Games
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations

Authors: Yuda Feng and Shi Li

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We give the first O(1)-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is e^{1/e} + ε ≈ 1.445 + ε, which matches the best known approximation ratio for the unweighted case [Barman et al., 2018]. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems [Shmoys and Tardos, 1993]. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most e^{1/e} ≈ 1.445 by Barman et al. [Barman et al., 2018], leading to our approximation ratio.

Cite as

Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 63:1-63:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2024.63,
  author =	{Feng, Yuda and Li, Shi},
  title =	{{A Note on Approximating Weighted Nash Social Welfare with Additive Valuations}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{63:1--63:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.63},
  URN =		{urn:nbn:de:0030-drops-202068},
  doi =		{10.4230/LIPIcs.ICALP.2024.63},
  annote =	{Keywords: Nash Social Welfare, Configuration LP, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Streaming Algorithms for Connectivity Augmentation

Authors: Ce Jin, Michael Kapralov, Sepideh Mahabadi, and Ali Vakilian

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We study the k-connectivity augmentation problem (k-CAP) in the single-pass streaming model. Given a (k-1)-edge connected graph G = (V,E) that is stored in memory, and a stream of weighted edges (also called links) L with weights in {0,1,… ,W}, the goal is to choose a minimum weight subset L' ⊆ L of the links such that G' = (V,E∪ L') is k-edge connected. We give a (2+ε)-approximation algorithm for this problem which requires to store O(ε^{-1} nlog n) words. Moreover, we show the tightness of our result: Any algorithm with better than 2-approximation for the problem requires Ω(n²) bits of space even when k = 2. This establishes a gap between the optimal approximation factor one can obtain in the streaming vs the offline setting for k-CAP. We further consider a natural generalization to the fully streaming model where both E and L arrive in the stream in an arbitrary order. We show that this problem has a space lower bound that matches the best possible size of a spanner of the same approximation ratio. Following this, we give improved results for spanners on weighted graphs: We show a streaming algorithm that finds a (2t-1+ε)-approximate weighted spanner of size at most O(ε^{-1} n^{1+1/t}log n) for integer t, whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on log W. We believe that this result is of independent interest. Using our spanner result, we provide an optimal O(t)-approximation for k-CAP in the fully streaming model with O(nk + n^{1+1/t}) words of space. Finally we apply our results to network design problems such as Steiner tree augmentation problem (STAP), k-edge connected spanning subgraph (k-ECSS) and the general Survivable Network Design problem (SNDP). In particular, we show a single-pass O(tlog k)-approximation for SNDP using O(kn^{1+1/t}) words of space, where k is the maximum connectivity requirement.

Cite as

Ce Jin, Michael Kapralov, Sepideh Mahabadi, and Ali Vakilian. Streaming Algorithms for Connectivity Augmentation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 93:1-93:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{jin_et_al:LIPIcs.ICALP.2024.93,
  author =	{Jin, Ce and Kapralov, Michael and Mahabadi, Sepideh and Vakilian, Ali},
  title =	{{Streaming Algorithms for Connectivity Augmentation}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{93:1--93:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.93},
  URN =		{urn:nbn:de:0030-drops-202367},
  doi =		{10.4230/LIPIcs.ICALP.2024.93},
  annote =	{Keywords: streaming algorithms, connectivity augmentation}
}
Document
Track A: Algorithms, Complexity and Games
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets

Authors: Yasushi Kawase, Koichi Nishimura, and Hanna Sumita

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
We study the problem of minimizing a given symmetric strictly convex function over the Minkowski sum of an integral base-polyhedron and an M-convex set. This problem has a hybrid of continuous and discrete structures. This emerges from the problem of allocating mixed goods, consisting of both divisible and indivisible goods, to agents with binary valuations so that the fairness measure, such as the Nash welfare, is maximized. It is known that both an integral base-polyhedron and an M-convex set have similar and nice properties, and the non-hybrid case can be solved in polynomial time. While the hybrid case lacks some of these properties, we show the structure of an optimal solution. Moreover, we exploit a proximity inherent in the problem. Through our findings, we demonstrate that our problem is NP-hard even in the fair allocation setting where all indivisible goods are identical. Moreover, we provide a polynomial-time algorithm for the fair allocation problem when all divisible goods are identical.

Cite as

Yasushi Kawase, Koichi Nishimura, and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ICALP.2024.96,
  author =	{Kawase, Yasushi and Nishimura, Koichi and Sumita, Hanna},
  title =	{{Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{96:1--96:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.96},
  URN =		{urn:nbn:de:0030-drops-202393},
  doi =		{10.4230/LIPIcs.ICALP.2024.96},
  annote =	{Keywords: Integral base-polyhedron, Fair allocation, Matroid}
}
Document
Track A: Algorithms, Complexity and Games
An Improved Quantum Max Cut Approximation via Maximum Matching

Authors: Eunou Lee and Ojas Parekh

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.

Cite as

Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 105:1-105:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ICALP.2024.105,
  author =	{Lee, Eunou and Parekh, Ojas},
  title =	{{An Improved Quantum Max Cut Approximation via Maximum Matching}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{105:1--105:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.105},
  URN =		{urn:nbn:de:0030-drops-202482},
  doi =		{10.4230/LIPIcs.ICALP.2024.105},
  annote =	{Keywords: approximation, optimization, local Hamiltonian, rounding, SDP, matching}
}
Document
An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems

Authors: Daniel Dadush, Zhuan Khye Koh, Bento Natura, and László A. Végh

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
We present an accelerated, or "look-ahead" version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains: (i) For linear fractional combinatorial optimization, we show a convergence bound of O(mlog m) iterations; the previous best bound was O(m²log m) by Wang et al. (2006). (ii) We obtain a strongly polynomial label-correcting algorithm for solving linear feasibility systems with two variables per inequality (2VPI). For a 2VPI system with n variables and m constraints, our algorithm runs in O(mn) iterations. Every iteration takes O(mn) time for general 2VPI systems, and O(m + nlog n) time for the special case of deterministic Markov Decision Processes (DMDPs). This extends and strengthens a previous result by Madani (2002) that showed a weakly polynomial bound for a variant of the Newton–Dinkelbach method for solving DMDPs. (iii) We give a simplified variant of the parametric submodular function minimization result by Goemans et al. (2017).

Cite as

Daniel Dadush, Zhuan Khye Koh, Bento Natura, and László A. Végh. An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dadush_et_al:LIPIcs.ESA.2021.36,
  author =	{Dadush, Daniel and Koh, Zhuan Khye and Natura, Bento and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{An Accelerated Newton-Dinkelbach Method and Its Application to Two Variables per Inequality Systems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.36},
  URN =		{urn:nbn:de:0030-drops-146172},
  doi =		{10.4230/LIPIcs.ESA.2021.36},
  annote =	{Keywords: Newton-Dinkelbach method, fractional optimization, parametric optimization, strongly polynomial algorithms, two variables per inequality systems, Markov decision processes, submodular function minimization}
}
Document
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and Their Applications

Authors: Jugal Garg, Edin Husić, and László A. Végh

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
We consider the Arrow-Debreu exchange market model where agents' demands satisfy the weak gross substitutes (WGS) property. This is a well-studied property, in particular, it gives a sufficient condition for the convergence of the classical tâtonnement dynamics. In this paper, we present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands. Such auction algorithms have been previously known for restricted classes of WGS demands only. As an application of our technique, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for NSW with budget separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.

Cite as

Jugal Garg, Edin Husić, and László A. Végh. Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and Their Applications. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.STACS.2021.33,
  author =	{Garg, Jugal and Husi\'{c}, Edin and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and Their Applications}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.33},
  URN =		{urn:nbn:de:0030-drops-136786},
  doi =		{10.4230/LIPIcs.STACS.2021.33},
  annote =	{Keywords: auction algorithm, weak gross substitutes, Fisher equilibrium, Gale equilibrium, Nash social welfare}
}
Document
Signed Tropical Convexity

Authors: Georg Loho and László A. Végh

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas' lemma and Fourier-Motzkin elimination without the non-negativity restriction on the variables. This leads to a Minkowski-Weyl theorem for polytopes over the signed tropical numbers.

Cite as

Georg Loho and László A. Végh. Signed Tropical Convexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 24:1-24:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{loho_et_al:LIPIcs.ITCS.2020.24,
  author =	{Loho, Georg and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{Signed Tropical Convexity}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{24:1--24:35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.24},
  URN =		{urn:nbn:de:0030-drops-117097},
  doi =		{10.4230/LIPIcs.ITCS.2020.24},
  annote =	{Keywords: tropical convexity, signed tropical numbers, Farkas' lemma}
}
Document
Complete Volume
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume

Authors: Dimitris Achlioptas and László A. Végh

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)


Abstract
LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume

Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Proceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019,
  title =	{{LIPIcs, Volume 145, APPROX/RANDOM'19, Complete Volume}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019},
  URN =		{urn:nbn:de:0030-drops-113014},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019},
  annote =	{Keywords: Mathematics of computing; Theory of computation}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dimitris Achlioptas and László A. Végh

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{achlioptas_et_al:LIPIcs.APPROX-RANDOM.2019.0,
  author =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{0:i--0:xxii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.0},
  URN =		{urn:nbn:de:0030-drops-112155},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Paper
Algorithms for the Asymmetric Traveling Salesman Problem (Invited Paper)

Authors: Ola Svensson

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)


Abstract
The traveling salesman problem is one of the most fundamental optimization problems. Given n cities and pairwise distances, it is the problem of finding a tour of minimum total distance that visits each city once. In spite of significant research efforts, current techniques seem insufficient for settling the approximability of the traveling salesman problem. The gap in our understanding is especially large in the general asymmetric setting where the distance from city i to j is not assumed to equal the distance from j to i. Indeed, until recently, it remained an open problem to design an algorithm with any constant approximation guarantee. This status is particularly intriguing as the standard linear programming relaxation is believed to give a constant-factor approximation algorithm, where the constant may in fact be as small as 2. In this talk, we will give an overview of old and new approaches for settling this question. We shall, in particular, talk about our new approach that gives the first constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. The main idea of our approach is to first give a generic reduction to structured instances and on those instances we then solve an easier problem (but equivalent in terms of constant-factor approximation) obtained by relaxing the general connectivity requirements into local connectivity conditions. This is based on joint work with Jakub Tarnawski and László A. Végh.

Cite as

Ola Svensson. Algorithms for the Asymmetric Traveling Salesman Problem (Invited Paper). In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{svensson:LIPIcs.FSTTCS.2018.3,
  author =	{Svensson, Ola},
  title =	{{Algorithms for the Asymmetric Traveling Salesman Problem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.3},
  URN =		{urn:nbn:de:0030-drops-99024},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.3},
  annote =	{Keywords: Approximation algorithms, combinatorial optimization, linear programming, traveling salesman problem}
}
Document
A 7/3-Approximation for Feedback Vertex Sets in Tournaments

Authors: Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first 7/3 approximation algorithm for this problem, improving on the previously best known ratio 5/2 given by Cai et al. [FOCS 1998, SICOMP 2001].

Cite as

Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A 7/3-Approximation for Feedback Vertex Sets in Tournaments. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{mnich_et_al:LIPIcs.ESA.2016.67,
  author =	{Mnich, Matthias and Vassilevska Williams, Virginia and V\'{e}gh, L\'{a}szl\'{o} A.},
  title =	{{A 7/3-Approximation for Feedback Vertex Sets in Tournaments}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.67},
  URN =		{urn:nbn:de:0030-drops-64098},
  doi =		{10.4230/LIPIcs.ESA.2016.67},
  annote =	{Keywords: Approximation algorithms, feedback vertex sets, tournaments}
}
  • Refine by Author
  • 6 Végh, László A.
  • 2 Achlioptas, Dimitris
  • 1 Dadush, Daniel
  • 1 Feng, Yuda
  • 1 Garg, Jugal
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing
  • 2 Mathematics of computing → Combinatorial optimization
  • 2 Theory of computation
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 2 Approximation algorithms
  • 1 Approximation Algorithms
  • 1 Conference Organization
  • 1 Configuration LP
  • 1 Fair allocation
  • Show More...

  • Refine by Type
  • 12 document
  • 1 volume

  • Refine by Publication Year
  • 5 2024
  • 3 2019
  • 2 2021
  • 1 2016
  • 1 2018
  • Show More...