Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The approximability of non-Boolean satisfiability problems and restricted integer programming

Autor
Serna, M.; Trevisan, L.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
Theoretical computer science
Data de publicació
2005-02
Volum
332
Número
1-3
Pàgina inicial
123
Pàgina final
139
DOI
https://doi.org/10.1016/j.tcs.2004.10.014 Obrir en finestra nova
URL
https://www.sciencedirect.com/science/article/pii/S0304397504007017 Obrir en finestra nova
Resum
In this paper we present improved approximation algorithms for two classes of maximization problems defined in Barland et al. (J. Comput. System Sci. 57(2) (1998) 144). Our factors of approximation substantially improve the previous known results and are close to the best possible. On the other hand, we show that the approximation results in the framework of Barland et al. hold also in the parallel setting, and thus we have a new common framework for both computational settings. We prove almost ...
Paraules clau
Maximum Capacity Representatives, Non-approximability, Non-boolean Constraint Satisfaction, Parallel Approximation Algorithms, Positive Linear Programming, Randomized Rounding
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants