Article

Differential approximation of MIN SAT, MAX SAT and related problems

Authors:

Vangelis Th. PaschosAuthors Info & Claims

ICCSA'05: Proceedings of the 2005 international conference on Computational Science and Its Applications - Volume Part IV

Pages 192 - 201

https://doi.org/10.1007/11424925_22

Published: 09 May 2005 Publication History

Abstract

We present differential approximation results (both positive and negative) for optimal satisfiability, optimal constraint satisfaction, and some of the most popular restrictive versions of them. As an important corollary, we exhibit an interesting structural difference between the landscapes of approximability classes in standard and differential paradigms.

References

[1]

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation. Combinatorial optimization problemsand their approximability properties. Springer, Berlin (1999)

Digital Library

Google Scholar

[2]

Vazirani, V.: Approximation algorithms. Springer, Berlin (2001)

Digital Library

Google Scholar

[3]

Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation and complexityclasses. J. Comput. System Sci. 43 (1991) 425-440

Crossref

Google Scholar

[4]

Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L.: Structure in approximationclasses. SIAM J. Comput. 28 (1999) 1759-1782

Digital Library

Google Scholar

[5]

Hooker, J.N.: Resolution vs. cutting plane solution of inference problems: somecomputational experience. Oper. Res. Lett. 7 (1988) 1-7

Digital Library

Google Scholar

[6]

Kamath, A.P., Karmarkar, N.K., Ramakrishnan, K.G., Resende, M.G.: Computationalexperience with an interior point algorithm on the satisfiability problem.Ann. Oper. Res. 25 (1990) 43-58

Digital Library

Google Scholar

[7]

Bazgan, C., Paschos, V.Th.: Differential approximation for optimal satisfiabilityand related problems. European J. Oper. Res. 147 (2003) 397-404

Crossref

Google Scholar

[8]

Monnot, J., Paschos, V. Th., Toulouse, S.: Approximation polynomiale des problèmesNP-difficiles : optima locaux et rapport différentiel. Hermès, Paris (2003)

Google Scholar

[9]

Escoffier, B., Paschos, V. Th.: Differential approximation of min sat, max satand related problems. Cahier du LAMSADE 220, LAMSADE, Université Paris-Dauphine (2004)

Google Scholar

[10]

Håstad, J.: Some optimal inapproximability results. J. Assoc. Comput. Mach. 48(2001) 798-859

Digital Library

Google Scholar

[11]

Bertsimas, D., Teo, C.P., Vohra, R.: On dependent randomized rounding algorithms.In: Proc. International Conference on Integer Programming and CombinatorialOptimization, IPCO. Volume 1084 of Lecture Notes in Computer Science., Springer-Verlag (1996) 330-344

Digital Library

Google Scholar

[12]

Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theoryof NP-completeness. W. H. Freeman, San Francisco (1979)

Digital Library

Google Scholar

Cited By

View all

Kimelfeld BRé C(2014)Transducing Markov sequencesJournal of the ACM10.1145/263006561:5(1-48)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2630065
Kimelfeld BRé CParedaens JVan Gucht D(2010)Transducing Markov sequencesProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807090(15-26)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807090

Index Terms

Differential approximation of MIN SAT, MAX SAT and related problems
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Mathematical optimization

Recommendations

Improved Approximation Algorithms for MAX SAT

MAX SAT (the maximum satisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approximation algorithms for MAX ...
Improved approximation algorithms for MAX NAE-SAT and MAX SAT
WAOA'05: Proceedings of the Third international conference on Approximation and Online Algorithms

MAX SAT and MAX NAE-SAT are central problems in theoretical computer science. We present an approximation algorithm for MAX NAE-SAT with a conjectured performance guarantee of 0.8279. This improves a previously conjectured performance guarantee of ...
Approximating Max NAE-k-SAT by anonymous local search

A clause is not-all-equal satisfied if it has at least one literal assigned with true and one literal assigned with false. Max NAE-SAT is given by a boolean variable set U and a clause set C, asks to find an assignment of U, such that the number of not-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCSA'05: Proceedings of the 2005 international conference on Computational Science and Its Applications - Volume Part IV

May 2005

1348 pages

ISBN:3540258639

Editors:
Osvaldo Gervasi
Department of Mathematics and Computer Science, University of Perugia, via Vanvitelli, 1, Perugia, Italy
,
Marina L. Gavrilova
Department of Computer Science, University of Calgary, 2500 University Drive N.W., Calgary, AB, Canada
,
Vipin Kumar
William Norris Professor, Head of the Computer Science and Engineering Department, University of Minnesota, 2500 University Drive N.W., Calgary, AB, Canada
,
Antonio Laganá
Department of Chemistry, University of Perugia, Via Elce di Sotto, 8, Perugia, AB, Italy
,
Heow Pueh Lee
Institute of High Performance Computing, IHCP, 1 Science Park Road, 01-01 The Capricorn, Singapore Science Park II, Perugia, AB, Singapore

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 May 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kimelfeld BRé C(2014)Transducing Markov sequencesJournal of the ACM10.1145/263006561:5(1-48)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2630065
Kimelfeld BRé CParedaens JVan Gucht D(2010)Transducing Markov sequencesProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807090(15-26)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807090

View Options

View options

Login options

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

Cited By

Index Terms

Recommendations

Improved Approximation Algorithms for MAX SAT

Improved approximation algorithms for MAX NAE-SAT and MAX SAT

Approximating Max NAE-k-SAT by anonymous local search