Approximability of Bounded Occurrence Max Ones

Simple item page
dc.creatorKuivinen, Fredrik
dc.date2006-06-13
dc.date.accessioned2026-07-07T07:13:04Z
dc.date.available2026-07-07T07:13:04Z
dc.descriptionWe 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.
dc.descriptionAccepted to MFCS 2006
dc.identifierhttps://arxiv.org/abs/cs/0606057
dc.identifierhttp://arxiv.org/abs/cs/0606057
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/112306
dc.subjectComputational Complexity
dc.titleApproximability of Bounded Occurrence Max Ones
dc.typetext

Files

Collections

arXiv