Search Results

Documents authored by Hu, Tingwei

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.60
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems

Authors: Lin Chen, Tingwei Hu, Yuchen Mao, Yong Chen, Lili Mei, An Zhang, Guangting Chen, and Guochuan Zhang

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

Abstract
In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our goal is to assign items to knapsacks so as to maximize the minimum profit received by any knapsack subject to the capacity constraint. When all knapsacks have identical capacity, we give a (2/3 - ε)-approximation algorithm for any constant ε > 0. This result almost matches the (2/3 + ε) inapproximability bound for the bottleneck multiple subset sum problem (Caprara et al., 2000). When the knapsacks can have arbitrary capacities, we propose a (1/2 - ε)-approximation algorithm for any constant ε > 0. We also prove a hardness bound of (1/2 + ε) for any constant ε > 0.
Cite as

Lin Chen, Tingwei Hu, Yuchen Mao, Yong Chen, Lili Mei, An Zhang, Guangting Chen, and Guochuan Zhang. Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 60:1-60:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.60,
  author =	{Chen, Lin and Hu, Tingwei and Mao, Yuchen and Chen, Yong and Mei, Lili and Zhang, An and Chen, Guangting and Zhang, Guochuan},
  title =	{{Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{60:1--60:19},
  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.60},
  URN =		{urn:nbn:de:0030-drops-264495},
  doi =		{10.4230/LIPIcs.ICALP.2026.60},
  annote =	{Keywords: Bottleneck multiple knapsack, approximation algorithms}
}
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