Approximability of Bounded Occurrence Max Ones
<|reference_start|>Approximability of Bounded Occurrence Max Ones: 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.<|reference_end|>
@article{kuivinen2006approximability,
    title={Approximability of Bounded Occurrence Max Ones},
    author={Fredrik Kuivinen},
    journal={arXiv preprint arXiv:cs/0606057},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0606057},
    primaryClass={cs.CC}
}