Skip to Main content Skip to Navigation
Conference papers

As Close as It Gets

Abstract : We study the minimum Hamming distance between distinct satisfying assignments of a conjunctive input formula over a given set of Boolean relations (???????????????????, ???). We present a complete classification of the complexity of this optimization problem with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness with respect to poly-APX, or NPO, or equivalence to a well-known hard optimization problem.
Document type :
Conference papers
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/hal-03300998
Contributor : Fabien Delorme <>
Submitted on : Tuesday, July 27, 2021 - 12:49:40 PM
Last modification on : Thursday, September 9, 2021 - 3:10:29 PM

Identifiers

  • HAL Id : hal-03300998, version 1

Collections

Citation

Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer. As Close as It Gets. 10th International Workshop on Algorithms and Computation (WALCOM '16), 2016, Kathmandu, Nepal. pp.222--235. ⟨hal-03300998⟩

Share

Metrics

Record views

7