Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

The Next Whisky Bar

Abstract : We determine the complexity of an optimization problem related to information theory. Taking a conjunctive propositional formula over some finite set of Boolean relations as input, we seek a satisfying assignment of the formula having minimal Hamming distance to a given assignment that is not required to be a model (NearestSolution, NSol). We obtain a complete classification with respect to the relations admitted in the formula. For two classes of constraint languages we present polynomial time algorithms; otherwise, we prove hardness or completeness concerning the classes APX, poly-APX, NPO, or equivalence to well-known hard optimization problems.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien DELORME Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 12:49:43 PM
Last modification on : Wednesday, November 3, 2021 - 9:13:32 AM


  • HAL Id : hal-03301002, version 1


Mike Behrisch, Miki Hermann, Stefan Mengel, Gernot Salzer. The Next Whisky Bar. 11th International Computer Science Symposium in Russia (CSR'16), 2016, St. Petersburg, Russia. pp.41--56. ⟨hal-03301002⟩



Record views