3 papers
cs.DS2026
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Lin Chen, Tingwei Hu, Yuchen Mao +5
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 go…
cs.GT2025
Maximizing social welfare among EF1 allocations at the presence of two types of agents
Jiaxuan Ma, Yong Chen, Guangting Chen +3
We study the fair allocation of indivisible items to agents to maximize the utilitarian social welfare, where the fairness criterion is envy-free up to one item and there are o…
cs.DS2024
Approximation algorithms for non-sequential star packing problems
Mengyuan Hu, An Zhang, Yong Chen +2
For a positive integer , a -star (-star, -star, respectively) is a connected graph containing a degree- vertex and degree- vertices, where $\e…