Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NPO PB-COMPLETE PROBLEMS:
Reports tagged with NPO PB-complete problems:
TR96-015 | 12th December 1995
Edoardo Amaldi, Viggo Kann

On the approximability of some NP-hard minimization problems for linear systems

We investigate the computational complexity of two classes of
combinatorial optimization problems related to linear systems
and study the relationship between their approximability properties.
In the first class (MIN ULR) one wishes, given a possibly infeasible
system of linear relations, to find ... more >>>




ISSN 1433-8092 | Imprint