Approximability of Bounded Occurrence Max Ones

Details Approximability of Bounded Occurrence Max Ones Approximability of Bounded Occurrence Max Ones

2006-06-13

arxiv.org/abs/cs/0606057v1

Computer Science

Computational Complexity

Accepted to MFCS 2006

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Approximability of Bounded Occurrence Max Ones does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximability of Bounded Occurrence Max Ones, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximability of Bounded Occurrence Max Ones will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-45928