Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of a recoloring is the sum of weights of vertices whose color changed. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm.
We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(log n)-competitive deterministic algorithm and an Ω(log n) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider a dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are weighted and the cost of recoloring a vertex is its weight. All our lower bounds hold even in the unweighted case.

Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou. Competitive Vertex Recoloring. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2022.13, author = {Azar, Yossi and Machluf, Chay and Patt-Shamir, Boaz and Touitou, Noam}, title = {{Competitive Vertex Recoloring}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {13:1--13:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.13}, URN = {urn:nbn:de:0030-drops-163542}, doi = {10.4230/LIPIcs.ICALP.2022.13}, annote = {Keywords: coloring with recourse, anti-affinity constraints} }

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 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.

Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz. Online Scheduling with Interval Conflicts. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 472-483, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.STACS.2011.472, author = {Halldorsson, Magnus M. and Patt-Shamir, Boaz and Rawitz, Dror}, title = {{Online Scheduling with Interval Conflicts}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {472--483}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.472}, URN = {urn:nbn:de:0030-drops-30363}, doi = {10.4230/LIPIcs.STACS.2011.472}, annote = {Keywords: online scheduling, online set packing, interval conflicts, competitive analysis, compound tasks, distributed algorithms} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

In the Multislope Ski Rental problem, the user needs a certain
resource for some unknown period of time. To use the resource, the
user must subscribe to one of several options, each of which
consists of a one-time setup cost (``buying price''), and cost
proportional to the duration of the usage (``rental rate''). The
larger the price, the smaller the rent. The actual usage time is
determined by an adversary, and the goal of an algorithm is to
minimize the cost by choosing the best option at any point in time.
Multislope Ski Rental is a natural generalization of the classical
Ski Rental problem (where the only options are pure rent and pure
buy), which is one of the fundamental problems of online
computation. The Multislope Ski Rental problem is an abstraction
of many problems where online decisions cannot be modeled by just
two options, e.g., power management in systems which can be shut
down in parts. In this paper we study randomized algorithms for
Multislope Ski Rental. Our results include the best possible
online randomized strategy for any additive instance, where the
cost of switching from one option to another is the difference in
their buying prices; and an algorithm that produces an
$e$-competitive randomized strategy for any (non-additive)
instance.

Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 503-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lotker_et_al:LIPIcs.STACS.2008.1331, author = {Lotker, Zvi and Patt-Shamir, Boaz and Rawitz, Dror}, title = {{Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {503--514}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1331}, URN = {urn:nbn:de:0030-drops-13313}, doi = {10.4230/LIPIcs.STACS.2008.1331}, annote = {Keywords: Competitive analysis, ski rental, randomized algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

We study the two party problem of randomly selecting a string among
all the strings of length n. We want the protocol to have the
property that the output distribution has high entropy, even
when one of the two parties is dishonest and deviates from the
protocol. We develop protocols that achieve high, close to n,
entropy.
In the literature the randomness guarantee is usually expressed as
being close to the uniform distribution or in terms of resiliency.
The notion of entropy is not directly comparable to that of
resiliency, but we establish a connection between the two that
allows us to compare our protocols with the existing ones.
We construct an
explicit protocol that yields entropy n - O(1) and has 4log^* n
rounds, improving over the protocol of Goldwasser
et al. that also achieves this entropy but needs O(n)
rounds. Both these protocols need O(n^2) bits of communication.
Next we reduce the communication in our protocols. We show the existence,
non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits
of communication and yields entropy n- O(log n) and min-entropy
n/2 - O(log n). Our protocol achieves the same entropy bound as
the recent, also non-explicit, protocol of Gradwohl
et al., however achieves much higher min-entropy: n/2 -
O(log n) versus O(log n).
Finally we exhibit very simple explicit protocols. We connect the
security parameter of these geometric protocols with the well
studied Kakeya problem motivated by harmonic analysis and analytical
number theory. We are only able to prove that these protocols have
entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore
they do not perform as well with respect to the explicit
constructions of Gradwohl et al. entropy-wise, but still
have much better min-entropy. We conjecture that these simple
protocols achieve n -o(n) entropy. Our geometric
construction and its relation to the Kakeya problem follows a new and
different approach to the random selection problem than any of the
previously known protocols.

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5, author = {Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz}, title = {{High Entropy Random Selection Protocols}}, booktitle = {Algebraic Methods in Computational Complexity}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {7411}, editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5}, URN = {urn:nbn:de:0030-drops-13091}, doi = {10.4230/DagSemProc.07411.5}, annote = {Keywords: Shannon entropy, Random string ds} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail