Showing 2025Show all
3 papers · 1 filter
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.DS2025
An improved local search based algorithm for -star partition
Mingyang Gong, Guohui Lin, Brendan Mumey
We study the -star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most vertices to cover all vertices in a simple undire…
cs.DS2025
Approximation algorithms for scheduling with rejection in green manufacturing
Mingyang Gong, Brendan Mumey
Motivated by green manufacturing, this paper investigates a scheduling with rejection problem subject to an energy consumption constraint. Machines are associated with non-uniform…