DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.17

Competitive Bundle Trading

Authors: Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Allocating a set of resources to an online sequence of customers is a fundamental problem in online algorithms with an extensive history. However, the natural extension where the algorithm is also allowed to purchase inventory from suppliers, who also arrive online, is essentially unexplored. We study this general trading problem under the objective of profit maximization, which is the difference between revenue from sales and cost of purchases. Maximizing the difference between two competing quantities is significantly more challenging than the sell-only case. We show a logarithmic competitive ratio relative to the optimal offline solution. Our algorithm is an exponential-weight–update dynamic pricing scheme, and our analysis dual-fits the algorithm’s profit with respect to a linear programming relaxation that upper bounds the optimal offline profit; we also prove (nearly) matching lower bounds. Finally, we extend our results by designing an incentive-compatible mechanism for the setting in which customers are strategic and may misreport their true valuations.

Cite as

Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi. Competitive Bundle Trading. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2026.17,
  author =	{Azar, Yossi and Buchbinder, Niv and Levin, Roie and Vardi, Or},
  title =	{{Competitive Bundle Trading}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.17},
  URN =		{urn:nbn:de:0030-drops-264066},
  doi =		{10.4230/LIPIcs.ICALP.2026.17},
  annote =	{Keywords: Online algorithms, competitive analysis, algorithmic game theory, mechanism design, dynamic pricing, resource allocation}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.18

Online Metric TSP: Beyond the √n Barrier

Authors: Yossi Azar, Debmalya Panigrahi, and Or Vardi

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study an online variant of the Traveling Salesperson Problem (TSP) in which n points arrive sequentially and must be inserted into an evolving tour. In the classical setting where arbitrary insertions are allowed, an O(log n)-competitive algorithm has been known since the 1970s (Rosenkrantz, Stearns and Lewis 1977, Imase and Waxman 1991). Recently, Abrahamsen, Bercea, Beretta, Klausen, and Kozma [ESA 2024] introduced online metric TSP, a stricter model in which each arriving point must be assigned to a distinct cell of an array of size m ≥ n, with the final tour order induced by the non-empty cells; the parameter m captures the space usage of the algorithm. When m = 2ⁿ, this model recovers arbitrary insertions and therefore admits an O(log n)-competitive algorithm. In contrast, when m = n, i.e., when each point’s position is fixed on arrival, Bertram [Christian Bertram, 2025] recently showed that the competitive ratio is Θ(√n). We investigate the tradeoff between space usage and competitiveness between these extremes. We note that this tradeoff was previously explored by the authors in [Yossi Azar et al., 2026] for the online sorting problem, which is the special case of online metric TSP on a line metric. Our main result is a deterministic online metric TSP algorithm using m = (1+ε) n space that achieves a competitive ratio of O(log³ n/ε), for any ε ≤ 1. In particular, increasing the space from n to 2n improves the competitive ratio from Θ(√n) to O(log³ n). We complement this with a lower bound showing that for m = n^{1+ε}, any deterministic algorithm has a competitive ratio Ω(1/ε), for all ε ≥ Ω(log log n / log n). Consequently, even with m = O(n ⋅ polylog(n)), deterministic algorithms cannot achieve a constant competitive ratio.

Cite as

Yossi Azar, Debmalya Panigrahi, and Or Vardi. Online Metric TSP: Beyond the √n Barrier. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2026.18,
  author =	{Azar, Yossi and Panigrahi, Debmalya and Vardi, Or},
  title =	{{Online Metric TSP: Beyond the √n Barrier}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.18},
  URN =		{urn:nbn:de:0030-drops-264071},
  doi =		{10.4230/LIPIcs.ICALP.2026.18},
  annote =	{Keywords: Online algorithms, competitive analysis, metric TSP, space-competitiveness tradeoff, routing problems}
}

Search Results

Documents authored by Vardi, Or

Competitive Bundle Trading

Abstract

Cite as

Online Metric TSP: Beyond the √n Barrier

Abstract

Cite as

Thanks for your feedback!

Could not send message