Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming

Autor
Serna, M.; Trevisan, L.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
Lecture notes in computer science
Data de publicació
1998
Volum
1373
Pàgina inicial
488
Pàgina final
498
DOI
https://doi.org/10.1007/BFb0028584 Obrir en finestra nova
URL
https://link.springer.com/chapter/10.1007/BFb0028584 Obrir en finestra nova
Resum
We present parallel approximation algorithms for maximization problems expressible by integer linear programs of a restricted syntactic form introduced by Barland et al. [BKT96]. One of our motivations was to show whether the approximation results in the framework of Barland et al. holds in the parallel setting. Our results are a confirmation of this, and thus we have a new common framework for both computational settings. Also, we prove almost tight non-approximability results, thus solving a m...
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants