| Files: |
Description |
File size |
Format |
| Fulltext |
|
PDF (requires Acrobat Reader) |
| Fulltext |
|
PostScript (requires a PostScript Reader) |
| |
|
| Author: |
Peter Jonsson |
| Article title: |
Tight Lower Bounds on the Approximability of Some NPO PB-Complete Problems |
| Publ. type: |
Article |
| Volume: |
2 |
| Article No: |
4 |
| Language: |
English |
| Abstract [en]: |
We investigate the approximability of the NPO
PB-complete problems MIN ONES, MIN DONES, MAX ONES, MAX DONES
and MAX PB 0/1 PROGRAMMING. We show that, unless P = NP, these problems
are not approximable within n1-ε} for any ε > 0 where n is the number of
variables in the input. Since all of these problems are approximable within
n, this lower bound is close to optimal. |
| PDF |
| Publisher: |
Linköping University Electronic Press |
| Year: |
1997 |
| Available: |
1997-04-11 |
| No. of pages: |
9 |
| Series: |
Linköping Electronic Articles in Computer and Information Science |
| ISSN: |
1401-9841 |
REFERENCE TO THIS PAGE:
| Jonsson, Peter (1997). Tight Lower Bounds on the Approximability of Some NPO PB-Complete Problems in Linköping Electronic Articles in Computer and Information Science, Vol. 2. http://www.ep.liu.se/ea/cis/1997/004/.
() |
|