Document

Complete Volume

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

LIPIcs, Volume 261, ICALP 2023, Complete Volume

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 1-2486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{etessami_et_al:LIPIcs.ICALP.2023, title = {{LIPIcs, Volume 261, ICALP 2023, Complete Volume}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {1--2486}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023}, URN = {urn:nbn:de:0030-drops-180517}, doi = {10.4230/LIPIcs.ICALP.2023}, annote = {Keywords: LIPIcs, Volume 261, ICALP 2023, Complete Volume} }

Document

Front Matter

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Front Matter, Table of Contents, Preface, Conference Organization

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 0:i-0:xxxviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{etessami_et_al:LIPIcs.ICALP.2023.0, author = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {0:i--0:xxxviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.0}, URN = {urn:nbn:de:0030-drops-180523}, doi = {10.4230/LIPIcs.ICALP.2023.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

In the well known planted clique problem, a clique (or alternatively, an independent set) of size k is planted at random in an Erdos-Renyi random G(n, p) graph, and the goal is to design an algorithm that finds the maximum clique (or independent set) in the resulting graph. We introduce a variation on this problem, where instead of planting the clique at random, the clique is planted by an adversary who attempts to make it difficult to find the maximum clique in the resulting graph. We show that for the standard setting of the parameters of the problem, namely, a clique of size k = √n planted in a random G(n, 1/2) graph, the known polynomial time algorithms can be extended (in a non-trivial way) to work also in the adversarial setting. In contrast, we show that for other natural settings of the parameters, such as planting an independent set of size k = n/2 in a G(n, p) graph with p = n^{-1/2}, there is no polynomial time algorithm that finds an independent set of size k, unless NP has randomized polynomial time algorithms.

Uriel Feige and Vadim Grinberg. How to Hide a Clique?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{feige_et_al:LIPIcs.ICALP.2020.44, author = {Feige, Uriel and Grinberg, Vadim}, title = {{How to Hide a Clique?}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {44:1--44:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.44}, URN = {urn:nbn:de:0030-drops-124517}, doi = {10.4230/LIPIcs.ICALP.2020.44}, annote = {Keywords: planted clique, semi-random model, Lovasz theta function, random graphs} }

Document

APPROX

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

A bipartite graph G(U,V;E) that admits a perfect matching is given. One player imposes a permutation pi over V, the other player imposes a permutation sigma over U. In the greedy matching algorithm, vertices of U arrive in order sigma and each vertex is matched to the highest (under pi) yet unmatched neighbor in V (or left unmatched, if all its neighbors are already matched). The obtained matching is maximal, thus matches at least a half of the vertices. The max-min greedy matching problem asks: suppose the first (max) player reveals pi, and the second (min) player responds with the worst possible sigma for pi, does there exist a permutation pi ensuring to match strictly more than a half of the vertices? Can such a permutation be computed in polynomial time?
The main result of this paper is an affirmative answer for these questions: we show that there exists a polytime algorithm to compute pi for which for every sigma at least rho > 0.51 fraction of the vertices of V are matched. We provide additional lower and upper bounds for special families of graphs, including regular and Hamiltonian graphs. Our solution solves an open problem regarding the welfare guarantees attainable by pricing in sequential markets with binary unit-demand valuations.

Alon Eden, Uriel Feige, and Michal Feldman. Max-Min Greedy Matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.APPROX-RANDOM.2019.7, author = {Eden, Alon and Feige, Uriel and Feldman, Michal}, title = {{Max-Min Greedy Matching}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {7:1--7:23}, 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.7}, URN = {urn:nbn:de:0030-drops-112229}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.7}, annote = {Keywords: Online matching, Pricing mechanism, Markets} }

Document

**Published in:** LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching.
Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.

Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{feige_et_al:LIPIcs.ICALP.2018.50, author = {Feige, Uriel and Patt-Shamir, Boaz and Vardi, Shai}, title = {{On the Probe Complexity of Local Computation Algorithms}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {50:1--50:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.50}, URN = {urn:nbn:de:0030-drops-90543}, doi = {10.4230/LIPIcs.ICALP.2018.50}, annote = {Keywords: Local computation algorithms, sublinear algorithms} }

Document

**Published in:** LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

The following paradigm is often used for handling NP-hard combinatorial optimization problems. One first formulates the problem as an integer program, then one relaxes it to a linear program (LP, or more generally, a convex program), then one solves the LP relaxation in polynomial time, and finally one rounds the optimal LP solution, obtaining a feasible solution to the original problem. Many of the commonly used rounding schemes (such as randomized rounding, threshold rounding and others) are "oblivious" in the sense that the rounding is performed based on the LP solution alone, disregarding the objective function. The goal of our work is to better understand in which cases oblivious rounding suffices in order to obtain approximation ratios that match the integrality gap of the underlying LP. Our study is information theoretic - the rounding is restricted to be oblivious but not restricted to run in polynomial time. In this information theoretic setting we characterize the approximation ratio achievable by oblivious rounding. It turns out to equal the integrality gap of the underlying LP on a problem that is the closure of the original combinatorial optimization problem. We apply our findings to the study of the approximation ratios obtainable by oblivious rounding for the maximum welfare problem, showing that when valuation functions are submodular oblivious rounding can match the integrality gap of the configuration LP (though we do not know what this integrality gap is), but when valuation functions are gross substitutes oblivious rounding cannot match the integrality gap (which is 1).

Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen. Oblivious Rounding and the Integrality Gap. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{feige_et_al:LIPIcs.APPROX-RANDOM.2016.8, author = {Feige, Uriel and Feldman, Michal and Talgam-Cohen, Inbal}, title = {{Oblivious Rounding and the Integrality Gap}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {8:1--8:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.8}, URN = {urn:nbn:de:0030-drops-66319}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.8}, annote = {Keywords: Welfare-maximization} }

Document

**Published in:** Dagstuhl Reports, Volume 1, Issue 6 (2011)

The Dagstuhl Seminar on ``Design and Analysis of Randomized and Approximation Algorithms'' (Seminar 11241) was held at Schloss Dagstuhl between June 13--17, 2011.
There were 26 regular talks and several informal and open problem session contributions presented during this seminar. Abstracts of the presentations have been put together in this seminar proceedings document together with some links to extended abstracts and full papers.

Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). In Dagstuhl Reports, Volume 1, Issue 6, pp. 24-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{dyer_et_al:DagRep.1.6.24, author = {Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek}, title = {{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)}}, pages = {24--53}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {6}, editor = {Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.6.24}, URN = {urn:nbn:de:0030-drops-32585}, doi = {10.4230/DagRep.1.6.24}, annote = {Keywords: Randomized Algorithms, Approximation Algorithms, Probabilistically Checkable Proofs, Approximation Hardness, Optimization Problems, Counting Problems, Streaming Algorithms, Random Graphs, Hypergraphs, Probabilistic Method, Networks, Linear Programs, Semidefinite Programs} }

Document

**Published in:** LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

In a combinatorial optimization problem, when given an input
instance, one seeks a feasible solution that optimizes the value
of the objective function. Many combinatorial optimization
problems are NP-hard. A way of coping with NP-hardness is by
considering approximation algorithms. These algorithms run in
polynomial time, and their performance is measured by their
approximation ratio: the worst case ratio between the value of the
solution produced and the value of the (unknown) optimal solution.
In some cases the design of approximation algorithms includes a
nonconstructive component. As a result, the algorithms become
estimation algorithms rather than approximation algorithms: they
allow one to estimate the value of the optimal solution, without
actually producing a solution whose value is close to optimal.
We shall present a few such examples, and discuss some open
questions.

Uriel Feige. On Estimation Algorithms vs Approximation Algorithms. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 357-363, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{feige:LIPIcs.FSTTCS.2008.1767, author = {Feige, Uriel}, title = {{On Estimation Algorithms vs Approximation Algorithms}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {357--363}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1767}, URN = {urn:nbn:de:0030-drops-17676}, doi = {10.4230/LIPIcs.FSTTCS.2008.1767}, annote = {Keywords: Estimation Algorithms, Approximation Algorithms, Combinatorial Optimization} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail