Found 2 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorithms which use these embeddings seem inherently randomized and ill-suited against adaptive adversaries.
In this paper we provide a new tree embedding which addresses these issues by deterministically embedding a graph into a single tree containing O(log n) copies of each vertex while preserving the connectivity structure of every subgraph and O(log² n)-approximating the cost of every subgraph. Using this embedding we obtain the first deterministic bicriteria approximation algorithm for the online covering Steiner problem as well as the first poly-log approximations for demand-robust Steiner forest, group Steiner tree and group Steiner forest.

Bernhard Haepler, D. Ellis Hershkowitz, and Goran Zuzic. Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{haepler_et_al:LIPIcs.ESA.2022.63, author = {Haepler, Bernhard and Hershkowitz, D. Ellis and Zuzic, Goran}, title = {{Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {63:1--63:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.63}, URN = {urn:nbn:de:0030-drops-170016}, doi = {10.4230/LIPIcs.ESA.2022.63}, annote = {Keywords: Tree metrics, metric embeddings, approximation algorithms, group Steiner forest, group Steiner tree, demand-robust algorithms, online algorithms, deterministic algorithms} }

Document

**Published in:** LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

We study how to vertex-sparsify a graph while preserving both the graph’s metric and structure. Specifically, we study the Steiner point removal (SPR) problem where we are given a weighted graph G = (V,E,w) and terminal set V' ⊆ V and must compute a weighted minor G' = (V',E', w') of G which approximates G’s metric on V'. A major open question in the area of metric embeddings is the existence of O(1) multiplicative distortion SPR solutions for every (non-trivial) minor-closed family of graphs. To this end prior work has studied SPR on trees, cactus and outerplanar graphs and showed that in these graphs such a minor exists with O(1) distortion.
We give O(1) distortion SPR solutions for series-parallel graphs, extending the frontier of this line of work. The main engine of our approach is a new metric decomposition for series-parallel graphs which we call a hammock decomposition. Roughly, a hammock decomposition is a forest-like structure that preserves certain critical parts of the metric induced by a series-parallel graph.

D. Ellis Hershkowitz and Jason Li. O(1) Steiner Point Removal in Series-Parallel Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hershkowitz_et_al:LIPIcs.ESA.2022.66, author = {Hershkowitz, D. Ellis and Li, Jason}, title = {{O(1) Steiner Point Removal in Series-Parallel Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {66:1--66:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.66}, URN = {urn:nbn:de:0030-drops-170041}, doi = {10.4230/LIPIcs.ESA.2022.66}, annote = {Keywords: Metric embeddings, graph algorithms, vertex sparsification} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

We study the store-and-forward packet routing problem for simultaneous multicasts, in which multiple packets have to be forwarded along given trees as fast as possible.
This is a natural generalization of the seminal work of Leighton, Maggs and Rao, which solved this problem for unicasts, i.e. the case where all trees are paths. They showed the existence of asymptotically optimal O(C + D)-length schedules, where the congestion C is the maximum number of packets sent over an edge and the dilation D is the maximum depth of a tree. This improves over the trivial O(CD) length schedules.
We prove a lower bound for multicasts, which shows that there do not always exist schedules of non-trivial length, o(CD). On the positive side, we construct O(C+D+log² n)-length schedules in any n-node network. These schedules are near-optimal, since our lower bound shows that this length cannot be improved to O(C+D) + o(log n).

Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. Near-Optimal Schedules for Simultaneous Multicasts. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 78:1-78:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ICALP.2021.78, author = {Haeupler, Bernhard and Hershkowitz, D. Ellis and Wajc, David}, title = {{Near-Optimal Schedules for Simultaneous Multicasts}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {78:1--78:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.78}, URN = {urn:nbn:de:0030-drops-141471}, doi = {10.4230/LIPIcs.ICALP.2021.78}, annote = {Keywords: Packet routing, multicast, scheduling algorithms} }

Document

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

Data aggregation is a fundamental primitive in distributed computing wherein a network computes a function of every nodes' input. However, while compute time is non-negligible in modern systems, standard models of distributed computing do not take compute time into account. Rather, most distributed models of computation only explicitly consider communication time.
In this paper, we introduce a model of distributed computation that considers both computation and communication so as to give a theoretical treatment of data aggregation. We study both the structure of and how to compute the fastest data aggregation schedule in this model. As our first result, we give a polynomial-time algorithm that computes the optimal schedule when the input network is a complete graph. Moreover, since one may want to aggregate data over a pre-existing network, we also study data aggregation scheduling on arbitrary graphs. We demonstrate that this problem on arbitrary graphs is hard to approximate within a multiplicative 1.5 factor. Finally, we give an O(log n ⋅ log(OPT/t_m))-approximation algorithm for this problem on arbitrary graphs, where n is the number of nodes and OPT is the length of the optimal schedule.

Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, and Ariel D. Procaccia. Computation-Aware Data Aggregation. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 65:1-65:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{haeupler_et_al:LIPIcs.ITCS.2020.65, author = {Haeupler, Bernhard and Hershkowitz, D. Ellis and Kahng, Anson and Procaccia, Ariel D.}, title = {{Computation-Aware Data Aggregation}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {65:1--65:38}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.65}, URN = {urn:nbn:de:0030-drops-117506}, doi = {10.4230/LIPIcs.ITCS.2020.65}, annote = {Keywords: Data aggregation, distributed algorithm scheduling, approximation algorithms} }

Document

**Published in:** LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random.
In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a non-adaptive protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of poly(log Delta, log log n) rounds where n is the number nodes in the network and Delta is the max degree. Moreover, we demonstrate that, even if the simulated protocol is not non-adaptive, it can be simulated with a multiplicative O(Delta log ^2 Delta) cost in the number of rounds. Lastly, we argue that simulations with a multiplicative overhead of o(log Delta) are unlikely to exist by proving that an Omega(log Delta) multiplicative round overhead is necessary under certain natural assumptions.

Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic. Erasure Correction for Noisy Radio Networks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2019.10, author = {Censor-Hillel, Keren and Haeupler, Bernhard and Hershkowitz, D. Ellis and Zuzic, Goran}, title = {{Erasure Correction for Noisy Radio Networks}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.10}, URN = {urn:nbn:de:0030-drops-113170}, doi = {10.4230/LIPIcs.DISC.2019.10}, annote = {Keywords: radio networks, erasure correction, noisy radio networks, protocol simulation, distributed computing models} }

Document

APPROX

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

In this paper we study how to optimally balance cheap inflexible resources with more expensive, reconfigurable resources despite uncertainty in the input problem. Specifically, we introduce the MinEMax model to study "build versus rent" problems. In our model different scenarios appear independently. Before knowing which scenarios appear, we may build rigid resources that cannot be changed for different scenarios. Once we know which scenarios appear, we are allowed to rent reconfigurable but expensive resources to use across scenarios. Although computing the objective in our model might seem to require enumerating exponentially-many possibilities, we show it is well estimated by a surrogate objective which is representable by a polynomial-size LP. In this surrogate objective we pay for each scenario only to the extent that it exceeds a certain threshold. Using this objective we design algorithms that approximately-optimally balance inflexible and reconfigurable resources for several NP-hard covering problems. For example, we study variants of minimum spanning and Steiner trees, minimum cuts, and facility location. Up to constants, our approximation guarantees match those of previously-studied algorithms for demand-robust and stochastic two-stage models. Lastly, we demonstrate that our problem is sufficiently general to smoothly interpolate between previous demand-robust and stochastic two-stage problems.

David Ellis Hershkowitz, R. Ravi, and Sahil Singla. Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hershkowitz_et_al:LIPIcs.APPROX-RANDOM.2019.4, author = {Hershkowitz, David Ellis and Ravi, R. and Singla, Sahil}, title = {{Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {4:1--4:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.4}, URN = {urn:nbn:de:0030-drops-112196}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.4}, annote = {Keywords: Approximation Algorithms, Optimization Under Uncertainty, Two-Stage Optimization, Expected Max} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail