Tingwei Hu

dblp:355/3038 · DBLP profile ↗
← Back
4ranked-venue papers
3as first author
4since 2021 · last 2026
0009-0005-0844-7506ORCID · reported

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 2 since 2021Artificial intelligence and machine learning · 1 · 1 first-author · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2026 Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
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.
Lin Chen 0009, Tingwei Hu, Yuchen Mao 0001, Yong Chen 0002, Lili Mei, An Zhang 0001, Guangting Chen, Guochuan Zhang
ICALP2
2026 Nearly tight bounds on the price of fairness for indivisible items under budget constraints
Tingwei Hu, Lili Mei, Zhen Wang 0013, Guochuan Zhang
Theor. Comput. Sci.1
2024 The Price of Fairness for Budget-Feasible EF1 Allocations
Tingwei Hu, Lili Mei, Zhen Wang 0013, Guochuan Zhang
COCOA (1)1
2023 Stackelberg Strategies on Epidemic Containment Games
Tingwei Hu, Lili Mei, Zhen Wang 0013
IJTCS-FAW1