4 Search Results for "Buchbinder, Niv"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.21
Metrical Service Systems with Transformations

Authors: Sébastien Bubeck, Niv Buchbinder, Christian Coester, and Mark Sellke

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which we call T-MSS, an algorithm maintains a point in a metric space and has to serve a sequence of requests. Each request is a map (transformation) f_t: A_t → B_t between subsets A_t and B_t of the metric space. To serve it, the algorithm has to go to a point a_t ∈ A_t, paying the distance from its previous position. Then, the transformation is applied, modifying the algorithm’s state to f_t(a_t). Such transformations can model, e.g., changes to the environment that are outside of an algorithm’s control, and we therefore do not charge any additional cost to the algorithm when the transformation is applied. The transformations also allow to model requests occurring in the k-taxi problem. We show that for α-Lipschitz transformations, the competitive ratio is Θ(α)^{n-2} on n-point metrics. Here, the upper bound is achieved by a deterministic algorithm and the lower bound holds even for randomized algorithms. For the k-taxi problem, we prove a competitive ratio of Õ((nlog k)²). For chasing convex bodies, we show that even with contracting transformations no competitive algorithm exists. The problem T-MSS has a striking connection to the following deep mathematical question: Given a finite metric space M, what is the required cardinality of an extension M̂ ⊇ M where each partial isometry on M extends to an automorphism? We give partial answers for special cases.
Cite as

Sébastien Bubeck, Niv Buchbinder, Christian Coester, and Mark Sellke. Metrical Service Systems with Transformations. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bubeck_et_al:LIPIcs.ITCS.2021.21,
  author =	{Bubeck, S\'{e}bastien and Buchbinder, Niv and Coester, Christian and Sellke, Mark},
  title =	{{Metrical Service Systems with Transformations}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.21},
  URN =		{urn:nbn:de:0030-drops-135608},
  doi =		{10.4230/LIPIcs.ITCS.2021.21},
  annote =	{Keywords: Online algorithms, competitive analysis, metrical task systems, k-taxi}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.6
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints

Authors: Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh

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

Abstract
We study the problem of maximizing a non-monotone submodular function subject to a cardinality constraint in the streaming model. Our main contributions are two single-pass (semi-)streaming algorithms that use Õ(k)⋅poly(1/ε) memory, where k is the size constraint. At the end of the stream, both our algorithms post-process their data structures using any offline algorithm for submodular maximization, and obtain a solution whose approximation guarantee is α/(1+α)-ε, where α is the approximation of the offline algorithm. If we use an exact (exponential time) post-processing algorithm, this leads to 1/2-ε approximation (which is nearly optimal). If we post-process with the algorithm of [Niv Buchbinder and Moran Feldman, 2019], that achieves the state-of-the-art offline approximation guarantee of α = 0.385, we obtain 0.2779-approximation in polynomial time, improving over the previously best polynomial-time approximation of 0.1715 due to [Feldman et al., 2018]. One of our algorithms is combinatorial and enjoys fast update and overall running times. Our other algorithm is based on the multilinear extension, enjoys an improved space complexity, and can be made deterministic in some settings of interest.
Cite as

Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alaluf_et_al:LIPIcs.ICALP.2020.6,
  author =	{Alaluf, Naor and Ene, Alina and Feldman, Moran and Nguyen, Huy L. and Suh, Andrew},
  title =	{{Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{6:1--6:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.6},
  URN =		{urn:nbn:de:0030-drops-124137},
  doi =		{10.4230/LIPIcs.ICALP.2020.6},
  annote =	{Keywords: Submodular maximization, streaming algorithms, cardinality constraint}
}
Document
DOI: 10.4230/LIPIcs.DISC.2018.35
Adapting Local Sequential Algorithms to the Distributed Setting

Authors: Ken-ichi Kawarabayashi and Gregory Schwartzman

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of the distributed algorithm will then be at least the number of colors. Surprisingly, this well known idea was never formally stated as a unified framework. In this paper we aim to define a robust family of local sequential algorithms which can be easily adapted to the distributed setting. We then develop new tools to further enhance these algorithms, achieving state of the art results for fundamental problems. We define a simple class of greedy-like algorithms which we call orderless-local algorithms. We show that given a legal c-coloring of the graph, every algorithm in this family can be converted into a distributed algorithm running in O(c) communication rounds in the CONGEST model. We show that this family is indeed robust as both the method of conditional expectations and the unconstrained submodular maximization algorithm of Buchbinder et al. [Niv Buchbinder et al., 2015] can be expressed as orderless-local algorithms for local utility functions - Utility functions which have a strong local nature to them. We use the above algorithms as a base for new distributed approximation algorithms for the weighted variants of some fundamental problems: Max k-Cut, Max-DiCut, Max 2-SAT and correlation clustering. We develop algorithms which have the same approximation guarantees as their sequential counterparts, up to a constant additive epsilon factor, while achieving an O(log^* n) running time for deterministic algorithms and O(epsilon^{-1}) running time for randomized ones. This improves exponentially upon the currently best known algorithms.
Cite as

Ken-ichi Kawarabayashi and Gregory Schwartzman. Adapting Local Sequential Algorithms to the Distributed Setting. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.DISC.2018.35,
  author =	{Kawarabayashi, Ken-ichi and Schwartzman, Gregory},
  title =	{{Adapting Local Sequential Algorithms to the Distributed Setting}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.35},
  URN =		{urn:nbn:de:0030-drops-98245},
  doi =		{10.4230/LIPIcs.DISC.2018.35},
  annote =	{Keywords: Distributed, Approximation Algorithms, Derandomization, Max-Cut}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.22
Online Algorithms for Maximum Cardinality Matching with Edge Arrivals

Authors: Niv Buchbinder, Danny Segev, and Yevgeny Tkach

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
In the adversarial edge arrival model for maximum cardinality matching, edges of an unknown graph are revealed one-by-one in arbitrary order, and should be irrevocably accepted or rejected. Here, the goal of an online algorithm is to maximize the number of accepted edges while maintaining a feasible matching at any point in time. For this model, the standard greedy heuristic is 1/2-competitive, and on the other hand, no algorithm that outperforms this ratio is currently known, even for very simple graphs. We present a clean Min-Index framework for devising a family of randomized algorithms, and provide a number of positive and negative results in this context. Among these results, we present a 5/9-competitive algorithm when the underlying graph is a forest, and prove that this ratio is best possible within the Min-Index framework. In addition, we prove a new general upper bound of 2/(3+1/phi^2) ~ 0.5914 on the competitiveness of any algorithm in the edge arrival model. Interestingly, this bound holds even for an easier model in which vertices (along with their adjacent edges) arrive online, and when the underlying graph is a tree of maximum degree at most 3.
Cite as

Niv Buchbinder, Danny Segev, and Yevgeny Tkach. Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchbinder_et_al:LIPIcs.ESA.2017.22,
  author =	{Buchbinder, Niv and Segev, Danny and Tkach, Yevgeny},
  title =	{{Online Algorithms for Maximum Cardinality Matching with Edge Arrivals}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.22},
  URN =		{urn:nbn:de:0030-drops-78206},
  doi =		{10.4230/LIPIcs.ESA.2017.22},
  annote =	{Keywords: Maximum matching, online algorithms, competitive analysis, primal-dual method}
}
  • Refine by Author
  • 2 Buchbinder, Niv
  • 1 Alaluf, Naor
  • 1 Bubeck, Sébastien
  • 1 Coester, Christian
  • 1 Ene, Alina
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Online algorithms
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 competitive analysis
  • 1 Approximation Algorithms
  • 1 Derandomization
  • 1 Distributed
  • 1 Max-Cut
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2017
  • 1 2018
  • 1 2020
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact