3 papers
cs.GT2026
Hospitals/Residents with Inseparable Couples: Finding a Coalition-Stable Assignment Is NP-Hard
Zeyuan Hu, C. Gregory Plaxton
In recent work on course allocation, RodrÃguez and Manlove consider the complexity of finding a stable assignment under four notions of stability, including two coalitional notion…
cs.DS2026
Moore's Greedy Algorithm for Minimizing the Number of Late Jobs: Structure and Implementation
Dean Matthew Menezes, C. Gregory Plaxton
Scheduling jobs with deadlines and processing times on a single resource to minimize late jobs equates to finding a maximum-cardinality feasible subset. Moore (1968) proposed a…
cs.GT2025
Constant-Approximate and Constant-Strategyproof Two-Facility Location
Elijah Journey Fullerton, Zeyuan Hu, C. Gregory Plaxton
We study deterministic mechanisms for the two-facility location problem. Given the reported locations of n agents on the real line, such a mechanism specifies where to build the tw…