Approximating integer programs with positive right-hand sides

Autor:	Johan Thapper, Peter Jonsson
Rok vydání:	2010
Předmět:	Combinatorics Unique games conjecture Bounded function Signal Processing Constraint matrix Minimisation (clinical trials) Computer Science Applications Information Systems Theoretical Computer Science Mathematics
Zdroj:	Information Processing Letters. 110:351-355
ISSN:	0020-0190
Popis:	We study minimisation of integer linear programs with positive right-hand sides. We show that such programs can be approximated within the maximum absolute row sum of the constraint matrix A whenever the variables are allowed to take values in N. This result is optimal under the unique games conjecture. When the variables are restricted to bounded domains, we show that finding a feasible solution is NP-hard in almost all cases.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::0692c6622519a449e5015be82d686b86 https://doi.org/10.1016/j.ipl.2010.02.011 Zobrazit plný text záznamu Full Text from ScienceDirect