Approximability of Bounded Occurrence Max Ones

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We study the approximability of Max Ones when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are included) we give a complete classification when the number of occurrences is three or more and a partial classification when the bound is two. For the non-conservative case we prove that it is either trivial or equivalent to the corresponding conservative problem under polynomial-time many-one reductions.
Accepted to MFCS 2006

Keywords

Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/112306

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0606057
 http://arxiv.org/abs/cs/0606057

Collections

arXiv