3 Search Results for "Shahar, Noa"

Document
DOI: 10.4230/LIPIcs.STACS.2026.27
The Communication Complexity of Combinatorial Auctions in Graphs

Authors: George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.
Cite as

George Christodoulou, Elias Koutsoupias, Annamária Kovács, and Ioannis Vlachos. The Communication Complexity of Combinatorial Auctions in Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.STACS.2026.27,
  author =	{Christodoulou, George and Koutsoupias, Elias and Kov\'{a}cs, Annam\'{a}ria and Vlachos, Ioannis},
  title =	{{The Communication Complexity of Combinatorial Auctions in Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.27},
  URN =		{urn:nbn:de:0030-drops-255163},
  doi =		{10.4230/LIPIcs.STACS.2026.27},
  annote =	{Keywords: Auctions, Communication Complexity, Mechanism Design, Graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.24
A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs

Authors: Keerti Choudhary and Rishabh Dhiman

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Afek, Bremler-Barr, Kaplan, Cohen, and Merritt (PODC'01) in their seminal work on shortest path restorations demonstrated that after a single edge failure in a graph G, a replacement shortest path between any two vertices s and t, which avoids the failed edge, can be represented as the concatenation of two original shortest paths in G. They also showed that we cannot associate a canonical shortest path between the vertex pairs in G that consistently allows for the replacement path (in the surviving graph) to be represented as a concatenation of these canonical paths. Recently, Bodwin and Parter (PODC'21) proposed a randomized tie-breaking scheme for selecting canonical paths for the "ordered" vertex pairs in graph G with the desired property of representing the replacement shortest path as a concatenation of canonical shortest-paths provided for ordered pairs. An interesting open question is whether it is possible to provide a deterministic construction of canonical paths in an efficient manner. We address this question in our paper by presenting an O(mn) time deterministic algorithm to compute a canonical path family ℱ = {P_{x,y}, Q_{x,y} | x,y ∈ V} comprising of two paths per (unordered) vertex pair. Each replacement is either a PQ-path (of type P_{x,y}∘Q_{y,z}), a QP-path, a QQ-path, or a PP-path. Our construction is fairly simple and is a straightforward application of independent spanning trees. We also present various applications of family ℱ in computing fault-tolerant structures.
Cite as

Keerti Choudhary and Rishabh Dhiman. A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 24:1-24:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.STACS.2025.24,
  author =	{Choudhary, Keerti and Dhiman, Rishabh},
  title =	{{A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{24:1--24:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.24},
  URN =		{urn:nbn:de:0030-drops-228499},
  doi =		{10.4230/LIPIcs.STACS.2025.24},
  annote =	{Keywords: Fault-tolerant Data-structures, Shortest Path Restoration, Replacement path}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.15
New Fault Tolerant Subset Preservers

Authors: Greg Bodwin, Keerti Choudhary, Merav Parter, and Noa Shahar

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

Abstract
Fault tolerant distance preservers are sparse subgraphs that preserve distances between given pairs of nodes under edge or vertex failures. In this paper, we present the first non-trivial constructions of subset distance preservers, which preserve all distances among a subset of nodes S, that can handle either an edge or a vertex fault. - For an n-vertex undirected weighted graph or weighted DAG G = (V,E) and S ⊆ V, we present a construction of a subset preserver with Õ(|S|n) edges that is resilient to a single fault. In the single pair case (|S| = 2), the bound improves to O(n). We further provide a nearly-matching lower bound of Ω(|S|n) in either setting, and we show that the same lower bound holds conditionally even if attention is restricted to unweighted graphs. - For an n-vertex directed unweighted graph G = (V,E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{4/3} |S|^{5/6}) edges that is resilient to a single fault. In the case |S| = 1 the bound improves to O(n^{4/3}), and for this case we provide another matching conditional lower bound. - For an n-vertex directed weighted graph G = (V, E) and r ∈ V, S ⊆ V, we present a construction of a preserver of distances in {r} × S with Õ(n^{3/2} |S|^{3/4}) edges that is resilient to a single vertex fault. (It was proved in [Greg Bodwin et al., 2017] that the bound improves to O(n^{3/2}) when |S| = 1, and that this is conditionally tight.)
Cite as

Greg Bodwin, Keerti Choudhary, Merav Parter, and Noa Shahar. New Fault Tolerant Subset Preservers. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ICALP.2020.15,
  author =	{Bodwin, Greg and Choudhary, Keerti and Parter, Merav and Shahar, Noa},
  title =	{{New Fault Tolerant Subset Preservers}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{15:1--15: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.15},
  URN =		{urn:nbn:de:0030-drops-124222},
  doi =		{10.4230/LIPIcs.ICALP.2020.15},
  annote =	{Keywords: Subset Preservers, Distances, Fault-tolerance}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2020

  • Refine by Author
  • 2 Choudhary, Keerti
  • 1 Bodwin, Greg
  • 1 Christodoulou, George
  • 1 Dhiman, Rishabh
  • 1 Koutsoupias, Elias
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Algorithmic mechanism design
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Computational pricing and auctions
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Auctions
  • 1 Communication Complexity
  • 1 Distances
  • 1 Fault-tolerance
  • 1 Fault-tolerant Data-structures
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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