3 Search Results for "Reiffenhäuser, Rebecca"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.94
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Authors: Yingxi Li, Ellen Vitercik, and Mingwei Yang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In the online metric matching problem, n servers and n requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in [0, 1]^d with the Euclidean metric, when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an O(1)-competitive algorithm for d ≠ 2 that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an o(log n) competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the Ω(log n) barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric space of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees.
Cite as

Yingxi Li, Ellen Vitercik, and Mingwei Yang. Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2026.94,
  author =	{Li, Yingxi and Vitercik, Ellen and Yang, Mingwei},
  title =	{{Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{94:1--94:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.94},
  URN =		{urn:nbn:de:0030-drops-253815},
  doi =		{10.4230/LIPIcs.ITCS.2026.94},
  annote =	{Keywords: Online algorithm, Metric matching, Competitive analysis, Smoothed analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.48
Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games

Authors: Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand, and Giovanna Varricchio

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A decade ago, Gerhard Woeginger posed an open problem that became well-known as "Woeginger’s Hiking Problem": Consider a group of n people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between 1 and n. Is it possible to efficiently assign the n people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition. We resolve the open problem in the affirmative by presenting an O(n⁵) time algorithm for Woeginger’s Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural, more demanding extensions of the problem, e.g., maximizing the number of satisfied participants and variants with single-peaked preferences, and show that they are also efficiently solvable. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games.
Cite as

Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand, and Giovanna Varricchio. Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.ICALP.2024.48,
  author =	{Constantinescu, Andrei and Lenzner, Pascal and Reiffenh\"{a}user, Rebecca and Schmand, Daniel and Varricchio, Giovanna},
  title =	{{Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.48},
  URN =		{urn:nbn:de:0030-drops-201910},
  doi =		{10.4230/LIPIcs.ICALP.2024.48},
  annote =	{Keywords: Algorithmic Game Theory, Dynamic Programming, Anonymous Hedonic Games, Single-Peaked Preferences, Social Optimum, Wonderful Partitions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.58
Truthful Matching with Online Items and Offline Agents

Authors: Michal Feldman, Federico Fusco, Simon Mauras, and Rebecca Reiffenhäuser

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

Abstract
We study truthful mechanisms for welfare maximization in online bipartite matching. In our (multi-parameter) setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier up to which the celebrated e/(e-1) competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.
Cite as

Michal Feldman, Federico Fusco, Simon Mauras, and Rebecca Reiffenhäuser. Truthful Matching with Online Items and Offline Agents. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feldman_et_al:LIPIcs.ICALP.2023.58,
  author =	{Feldman, Michal and Fusco, Federico and Mauras, Simon and Reiffenh\"{a}user, Rebecca},
  title =	{{Truthful Matching with Online Items and Offline Agents}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{58:1--58:20},
  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.58},
  URN =		{urn:nbn:de:0030-drops-181106},
  doi =		{10.4230/LIPIcs.ICALP.2023.58},
  annote =	{Keywords: Online matching, Karp-Vazirani-Vazirani, truthfulness}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2024
  • 1 2023

  • Refine by Author
  • 2 Reiffenhäuser, Rebecca
  • 1 Constantinescu, Andrei
  • 1 Feldman, Michal
  • 1 Fusco, Federico
  • 1 Lenzner, Pascal
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Online algorithms
  • 1 Applied computing → Online auctions
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Dynamic programming

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Anonymous Hedonic Games
  • 1 Competitive analysis
  • 1 Dynamic Programming
  • 1 Karp-Vazirani-Vazirani
  • 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