Article

The Next Whisky Bar

Authors:

Mike Behrisch,

Miki Hermann,

Stefan Mengel,

Gernot SalzerAuthors Info & Claims

CSR 2016: Proceedings of the 11th International Computer Science Symposium on Computer Science --- Theory and Applications - Volume 9691

Pages 41 - 56

https://doi.org/10.1007/978-3-319-34171-2_4

Published: 09 June 2016 Publication History

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.

References

[1]

Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 542, 317---331 1997

Digital Library

Google Scholar

[2]

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg 1999

Digital Library

Google Scholar

[3]

Bailleux, O., Marquis, P.: Some computational aspects of Distance-SAT. J. Autom. Reasoning 374, 231---260 2006

Digital Library

Google Scholar

[4]

Behrisch, M., Hermann, M., Mengel, S., Salzer, G.: Give me another one!. In: Elbassioni, K., Makino, K. eds. ISAAC 2015. LNCS, vol. 9472, pp. 664---676. Springer, Heidelberg 2015.

Crossref

Google Scholar

[5]

Behrisch, M., Hermann, M., Mengel, S., Salzer, G.: As close as it gets. In: Kaykobad, M., Petreschi, R. eds. WALCOM 2016. LNCS, vol. 9627, pp. 222---235. Springer, Heidelberg 2016.

Crossref

Google Scholar

[6]

Böhler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part II: constraint satisfaction problems. SIGACT News, Complex. Theor. Column 43 351, 22---35 2004

Google Scholar

[7]

Böhler, E., Reith, S., Schnoor, H., Vollmer, H.: Bases for Boolean co-clones. Inf. Process. Lett. 962, 59---66 2005

Digital Library

Google Scholar

[8]

Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia PA 2001

Digital Library

Google Scholar

[9]

Hochbaum, D.S., Megiddo, N., Naor, J., Tamir, A.: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 621---3, 69---83 1993

Google Scholar

[10]

Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM J. Comput. 306, 1863---1920 2000

Digital Library

Google Scholar

[11]

Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Symposium on Theory of Computing STOC 1978, San Diego, pp. 216---226 1978

Digital Library

Google Scholar

[12]

Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons, New York 1986

Digital Library

Google Scholar

The Next Whisky Bar
1. Theory of computation

Recommendations

Acyclic automata and small expressions using multi-tilde-bar operators

A regular expression with n occurrences of symbol can be converted into an equivalent automaton with (n+1) states, the so-called Glushkov automaton of the expression. Conversely, it is possible to decide whether a given (n+1)-state automaton is a ...
Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee
SODA '16: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms

The standard parameterization of the Vertex Cover problem (Given an undirected graph G and k ∈ N as input, does G have a vertex cover of size at most k?) has the solution size k as the parameter. The following more challenging parameterization of Vertex ...
Extended to multi-tilde-bar regular expressions and efficient finite automata constructions

Several algorithms have been designed to convert a regular expression into an equivalent finite automaton. One of the most popular constructions, due to Glushkov and to McNaughton and Yamada, is based on the computation of the Null, First, Last and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CSR 2016: Proceedings of the 11th International Computer Science Symposium on Computer Science --- Theory and Applications - Volume 9691

June 2016

424 pages

ISBN:9783319341705

Editors:
Alexander S. Kulikov
Russian Academy of Sciences, St. Petersburg, Russia
,
Gerhard J. Woeginger
Technische Universiteit Eindhoven, Eindhoven, The Netherlands

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 June 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Recommendations

Acyclic automata and small expressions using multi-tilde-bar operators

Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee

Extended to multi-tilde-bar regular expressions and efficient finite automata constructions

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations