5 Search Results for "Slivkins, Aleksandrs"

Document
DOI: 10.4230/LIPIcs.ESA.2025.115
Smoothed Analysis of Online Metric Problems

Authors: Christian Coester and Jack Umenberger

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We study three classical online problems - k-server, k-taxi, and chasing size k sets - through a lens of smoothed analysis. Our setting allows request locations to be adversarial up to small perturbations, interpolating between worst-case and average-case models. Specifically, we show that if the metric space is contained in a ball in any normed space and requests are drawn from distributions whose density functions are upper bounded by 1/σ times the uniform density over the ball, then all three problems admit polylog(k/σ)-competitive algorithms. Our approach is simple: it reduces smoothed instances to fully adversarial instances on finite metrics and leverages existing algorithms in a black-box manner. We also provide a lower bound showing that no algorithm can achieve a competitive ratio sub-polylogarithmic in k/σ, matching our upper bounds up to the exponent of the polylogarithm. In contrast, the best known competitive ratios for these problems in the fully adversarial setting are 2k-1, ∞ and Θ(k²), respectively.
Cite as

Christian Coester and Jack Umenberger. Smoothed Analysis of Online Metric Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{coester_et_al:LIPIcs.ESA.2025.115,
  author =	{Coester, Christian and Umenberger, Jack},
  title =	{{Smoothed Analysis of Online Metric Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{115:1--115:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.115},
  URN =		{urn:nbn:de:0030-drops-245847},
  doi =		{10.4230/LIPIcs.ESA.2025.115},
  annote =	{Keywords: Online Algorithms, Competitive Analysis, Smoothed Analysis, k-server, k-taxi, Metrical Service Systems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.90
Revisiting Directed Disjoint Paths on Tournaments (And Relatives)

Authors: Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when c ≤ k/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is W[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal.
Cite as

Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau. Revisiting Directed Disjoint Paths on Tournaments (And Relatives). In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 90:1-90:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dec.m.gomes_et_al:LIPIcs.ICALP.2025.90,
  author =	{de C. M. Gomes, Guilherme and Lopes, Raul and Sau, Ignasi},
  title =	{{Revisiting Directed Disjoint Paths on Tournaments (And Relatives)}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{90:1--90:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.90},
  URN =		{urn:nbn:de:0030-drops-234678},
  doi =		{10.4230/LIPIcs.ICALP.2025.90},
  annote =	{Keywords: directed graphs, tournaments, semicomplete digraphs, directed disjoint paths, congestion, parameterized complexity, directed pathwidth}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.12
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Authors: Aditya Anand, Euiwoong Lee, Jason Li, and Thatchaphol Saranurak

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a directed graph G with n vertices and m edges, a parameter k and two disjoint subsets S,T ⊆ V(G), we show that the number of all-subsets important separators, which is the number of A-B important vertex separators of size at most k over all A ⊆ S and B ⊆ T, is at most β(|S|, |T|, k) = 4^k binom(|S|, ≤ k) binom(|T|, ≤ 2k), where binom(x, ≤ c) = ∑_{i = 1}^c binom(x,i), and that they can be enumerated in time 𝒪(β(|S|,|T|,k)k²(m+n)). This is a generalization of the folklore result stating that the number of A-B important separators for two fixed sets A and B is at most 4^k (first implicitly shown by Chen, Liu and Lu Algorithmica '09). From this result, we obtain the following applications: 1) We give a construction for detection sets and sample sets in directed graphs, generalizing the results of Kleinberg (Internet Mathematics' 03) and Feige and Mahdian (STOC' 06) to directed graphs. 2) Via our new sample sets, we give the first FPT algorithm for finding balanced separators in directed graphs parameterized by k, the size of the separator. Our algorithm runs in time 2^{𝒪(k)} ⋅ (m + n). 3) Additionally, we show a 𝒪(√{log k}) approximation algorithm for finding balanced separators in directed graphs in polynomial time. This improves the best known approximation guarantee of 𝒪(√{log n}) and matches the known guarantee in undirected graphs by Feige, Hajiaghayi and Lee (SICOMP' 08). 4) Finally, using our algorithm for listing all-subsets important separators, we give a deterministic construction of vertex cut sparsifiers in directed graphs when we are interested in preserving min-cuts of size upto c between bipartitions of the terminal set. Our algorithm constructs a sparsifier of size 𝒪(binom(t, ≤ 3c)2^{𝒪(c)}) and runs in time 𝒪(binom(t, ≤ 3c) 2^{𝒪(c)}(m + n)), where t is the number of terminals, and the sparsifier additionally preserves the set of important separators of size at most c between bipartitions of the terminals.
Cite as

Aditya Anand, Euiwoong Lee, Jason Li, and Thatchaphol Saranurak. All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.ICALP.2025.12,
  author =	{Anand, Aditya and Lee, Euiwoong and Li, Jason and Saranurak, Thatchaphol},
  title =	{{All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.12},
  URN =		{urn:nbn:de:0030-drops-233892},
  doi =		{10.4230/LIPIcs.ICALP.2025.12},
  annote =	{Keywords: directed graphs, important separators, sample sets, balanced separators}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.52
Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence

Authors: Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Online advertising via auctions increasingly dominates the marketing landscape. A typical advertiser may participate in thousands of auctions each day with bids tailored to a variety of signals about user demographics and intent. These auctions are strategically linked through a global budget constraint. To help address the difficulty of bidding, many major online platforms now provide automated budget management via a flexible approach called budget pacing: rather than bidding directly, an advertiser specifies a global budget target and a maximum willingness-to-pay for different types of advertising opportunities. The specified maximums are then scaled down (or "paced") by a multiplier so that the realized total spend matches the target budget. These automated bidders are now near-universally adopted across all mature advertising platforms, raising pressing questions about market outcomes that arise when advertisers use budget pacing simultaneously. In this paper we study the aggregate welfare and individual regret guarantees of dynamic pacing algorithms in repeated auctions with budgets. We show that when agents simultaneously use a natural form of gradient-based pacing, the liquid welfare obtained over the course of the dynamics is at least half the optimal liquid welfare obtainable by any allocation rule, matching the best possible bound for static auctions even in pure Nash equilibria [Aggarwal et al., WINE 2019; Babaioff et al., ITCS 2021]. In contrast to prior work, these results hold without requiring convergence of the dynamics, circumventing known computational obstacles of finding equilibria [Chen et al., EC 2021]. Our result is robust to the correlation structure among agents' valuations and holds for any core auction, a broad class that includes first-price, second-price, and GSP auctions. We complement the aggregate guarantees by showing that an agent using such pacing algorithms achieves an O(T^{3/4}) regret relative to the value obtained by the best fixed pacing multiplier in hindsight in stochastic bidding environments. Compared to past work, this result applies to more general auctions and extends to adversarial settings with respect to dynamic regret.
Cite as

Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, and Aleksandrs Slivkins. Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 52:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gaitonde_et_al:LIPIcs.ITCS.2023.52,
  author =	{Gaitonde, Jason and Li, Yingkai and Light, Bar and Lucier, Brendan and Slivkins, Aleksandrs},
  title =	{{Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{52:1--52:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.52},
  URN =		{urn:nbn:de:0030-drops-175557},
  doi =		{10.4230/LIPIcs.ITCS.2023.52},
  annote =	{Keywords: repeated auctions with budgets, pacing, learning in auctions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.48
Competing Bandits: Learning Under Competition

Authors: Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Most modern systems strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We initiate a study of the interplay between exploration and competition--how such systems balance the exploration for learning and the competition for users. Here the users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing systems. In our model, we consider competition between two multi-armed bandit algorithms faced with the same bandit instance. Users arrive one by one and choose among the two algorithms, so that each algorithm makes progress if and only if it is chosen. We ask whether and to what extent competition incentivizes the adoption of better bandit algorithms. We investigate this issue for several models of user response, as we vary the degree of rationality and competitiveness in the model. Our findings are closely related to the "competition vs. innovation" relationship, a well-studied theme in economics.
Cite as

Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu. Competing Bandits: Learning Under Competition. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 48:1-48:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mansour_et_al:LIPIcs.ITCS.2018.48,
  author =	{Mansour, Yishay and Slivkins, Aleksandrs and Wu, Zhiwei Steven},
  title =	{{Competing Bandits: Learning Under Competition}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{48:1--48:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.48},
  URN =		{urn:nbn:de:0030-drops-83341},
  doi =		{10.4230/LIPIcs.ITCS.2018.48},
  annote =	{Keywords: machine learning, game theory, competition, exploration, rationality}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2023
  • 1 2018

  • Refine by Author
  • 2 Slivkins, Aleksandrs
  • 1 Anand, Aditya
  • 1 Coester, Christian
  • 1 Gaitonde, Jason
  • 1 Lee, Euiwoong
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Convergence and learning in games
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 2 directed graphs
  • 1 Competitive Analysis
  • 1 Metrical Service Systems
  • 1 Online Algorithms
  • 1 Smoothed Analysis
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact