| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142530 | Operations Research Letters | 2014 | 6 Pages |
Abstract
We show that the most cost-efficient subset problem for linear programming games is NP-hard, and in fact inapproximable within a constant factor in polynomial time, unless P=NPP=NP. This in turn implies that computing the prices output by an egalitarian mechanism and computing a cost allocation in the equal split-off set for linear programming games is NP-hard.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nelson A. Uhan,