5 Search Results for "Jin, Billy"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.21
Dual Charging for Half-Integral TSP

Authors: Nathan Klein and Mehrshad Taziki

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
In this extended abstract, we show that the max entropy algorithm is a randomized 1.49776 approximation for half-integral TSP, improving upon the previous known bound of 1.49993 from Karlin et al. This also improves upon the best-known approximation for half-integral TSP due to Gupta et al. Our improvement results from using the dual, instead of the primal, to analyze the expected cost of the matching. We believe this method of analysis could lead to a simpler proof that max entropy is a better-than-3/2 approximation in the general case.
Cite as

Nathan Klein and Mehrshad Taziki. Dual Charging for Half-Integral TSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{klein_et_al:LIPIcs.APPROX/RANDOM.2025.21,
  author =	{Klein, Nathan and Taziki, Mehrshad},
  title =	{{Dual Charging for Half-Integral TSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.21},
  URN =		{urn:nbn:de:0030-drops-243879},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.21},
  annote =	{Keywords: Approximation Algorithms, Graph Algorithms, Randomized Rounding, Linear Programming}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.12
Online Knapsack Problems with Estimates

Authors: Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ± δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.
Cite as

Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker. Online Knapsack Problems with Estimates. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.12,
  author =	{Balab\'{a}n, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
  title =	{{Online Knapsack Problems with Estimates}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.12},
  URN =		{urn:nbn:de:0030-drops-241190},
  doi =		{10.4230/LIPIcs.MFCS.2025.12},
  annote =	{Keywords: Knapsack, Online Knapsack, Removability, Estimate, Prediction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.58
A New Impossibility Result for Online Bipartite Matching Problems

Authors: Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, and Andrea Vattani

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

Abstract
Online Bipartite Matching with random user arrival is a fundamental problem in the online advertisement ecosystem. Over the last 30 years, many algorithms and impossibility results have been developed for this problem. In particular, the latest impossibility result was established by Manshadi, Oveis Gharan and Saberi [Manshadi et al., 2011] in 2011. Since then, several algorithms have been published in an effort to narrow the gap between the upper and the lower bounds on the competitive ratio. In this paper we show that no algorithm can achieve a competitive ratio better than 1- e/(e^e) = 0.82062…, improving upon the 0.823 upper bound presented in [Manshadi et al., 2011]. Our construction is simple to state, accompanied by a fully analytic proof, and yields a competitive ratio bound intriguingly similar to 1 - 1/e, the optimal competitive ratio for the fully adversarial Online Bipartite Matching problem. Although the tightness of our upper bound remains an open question, we show that our construction is extremal in a natural class of instances.
Cite as

Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, and Andrea Vattani. A New Impossibility Result for Online Bipartite Matching Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chierichetti_et_al:LIPIcs.ICALP.2025.58,
  author =	{Chierichetti, Flavio and Giacchini, Mirko and Panconesi, Alessandro and Vattani, Andrea},
  title =	{{A New Impossibility Result for Online Bipartite Matching Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{58:1--58: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.58},
  URN =		{urn:nbn:de:0030-drops-234354},
  doi =		{10.4230/LIPIcs.ICALP.2025.58},
  annote =	{Keywords: Bipartite Matching, Random Graphs, Competitive Ratio}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.98
The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang

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

Abstract
We study the online allocation of divisible items to n agents with additive valuations for p-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti (2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of -∞ ≤ p ≤ 1. Surprisingly, our improved algorithms for all p ≤ (1)/(log n) are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.
Cite as

Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 98:1-98:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2025.98,
  author =	{Huang, Zhiyi and Lee, Chui Shan and Shu, Xinkai and Wang, Zhaozi},
  title =	{{The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{98:1--98:18},
  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.98},
  URN =		{urn:nbn:de:0030-drops-234754},
  doi =		{10.4230/LIPIcs.ICALP.2025.98},
  annote =	{Keywords: Online Algorithms, Fair Division, Nash Welfare}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.69
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems

Authors: Monika Henzinger, Billy Jin, Richard Peng, and David P. Williamson

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

Abstract
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1-ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.
Cite as

Monika Henzinger, Billy Jin, Richard Peng, and David P. Williamson. A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ITCS.2023.69,
  author =	{Henzinger, Monika and Jin, Billy and Peng, Richard and Williamson, David P.},
  title =	{{A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{69:1--69:22},
  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.69},
  URN =		{urn:nbn:de:0030-drops-175720},
  doi =		{10.4230/LIPIcs.ITCS.2023.69},
  annote =	{Keywords: Laplacian solver, electrical flow, data structure}
}
  • Refine by Type
  • 5 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2023

  • Refine by Author
  • 1 Balabán, Jakub
  • 1 Chierichetti, Flavio
  • 1 Gehnen, Matthias
  • 1 Giacchini, Mirko
  • 1 Henzinger, Monika
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Online algorithms
  • 1 Theory of computation → Network flows
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Bipartite Matching
  • 1 Competitive Ratio
  • 1 Estimate
  • 1 Fair Division
  • 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