Search results for "Max-2-SAT"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
87	Michael Lewin, Dror Livnat, Uri Zwick	Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems.	IPCO	2002	DBLP DOI BibTeX RDF
85	Martin Fürer, Shiva Prasad Kasiviswanathan	Exact Max 2-Sat: Easier and Faster.	SOFSEM (1)	2007	DBLP DOI BibTeX RDF
78	Lars Engebretsen, Venkatesan Guruswami	Is Constraint Satisfaction Over Two Variables Always Easy?	RANDOM	2002	DBLP DOI BibTeX RDF
67	Arist Kojevnikov, Alexander S. Kulikov	A new approach to proving upper bounds for MAX-2-SAT.	SODA	2006	DBLP DOI BibTeX RDF
58	Serge Gaspers, Gregory B. Sorkin	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.	SODA	2009	DBLP DOI BibTeX RDF
49	Haiou Shen, Hantao Zhang 0001	Improving exact algorithms for MAX-2-SAT.	Ann. Math. Artif. Intell.	2005	DBLP DOI BibTeX RDF	exact algorithms, propositional satisfiability, maximum satisfiability
45	Per Austrin	Balanced max 2-sat might not be the hardest.	STOC	2007	DBLP DOI BibTeX RDF	Max 2-Sat, inapproximability, unique games conjecture
39	Jordi Planes	Improved Branch and Bound Algorithms for Max-2-SAT and Weighted Max-2-SAT.	CP	2003	DBLP DOI BibTeX RDF
36	Alexander S. Kulikov, Konstantin Kutzkov	New Bounds for MAX-SAT by Clause Learning.	CSR	2007	DBLP DOI BibTeX RDF
36	Carla P. Gomes, Willem Jan van Hoeve, Lucian Leahu	The Power of Semidefinite Programming Relaxations for MAX-SAT.	CPAIOR	2006	DBLP DOI BibTeX RDF
31	Daniel Raible 0001, Henning Fernau	A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach.	MFCS	2008	DBLP DOI BibTeX RDF
31	Thomas Hofmeister	An Approximation Algorithm for MAX-2-SAT with Cardinality Constraint.	ESA	2003	DBLP DOI BibTeX RDF
29	Alexander D. Scott, Gregory B. Sorkin	An LP-Designed Algorithm for Constraint Satisfaction.	ESA	2006	DBLP DOI BibTeX RDF
29	Ryan Williams 0001	A New Algorithm for Optimal Constraint Satisfaction and Its Implications.	ICALP	2004	DBLP DOI BibTeX RDF
28	Serge Gaspers, Gregory B. Sorkin	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.	J. Comput. Syst. Sci.	2012	DBLP DOI BibTeX RDF
28	Alexander Golovnev	New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree.	IPEC	2011	DBLP DOI BibTeX RDF
28	Serge Gaspers, Gregory B. Sorkin	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between	CoRR	2009	DBLP BibTeX RDF
28	Alexander D. Scott, Gregory B. Sorkin	Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP	CoRR	2006	DBLP BibTeX RDF
28	Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith	Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.	Discret. Appl. Math.	2003	DBLP DOI BibTeX RDF
28	Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, Peter Rossmanith	New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT	Electron. Colloquium Comput. Complex.	2000	DBLP BibTeX RDF
27	Mihir Bellare, Oded Goldreich 0001, Madhu Sudan 0001	Free Bits, PCPs and Non-Approximability - Towards Tight Results.	FOCS	1995	DBLP DOI BibTeX RDF	free bits, logarithmic randomness, amortized free bits, Max Clique, Max-2-SAT, FGLSS connection, amortized free-bit complexity, amortized free bit complexity, FPCP parameters, triviality results, computational complexity, computational geometry, theorem proving, NP-hardness, NP complete problems, proof systems, chromatic number, PCPs, Max-cut, nonapproximability
26	David R. Karger, Rajeev Motwani 0001, Madhu Sudan 0001	Approximate Graph Coloring by Semidefinite Programming	FOCS	1994	DBLP DOI BibTeX RDF	approximate graph coloring, k-colorable graphs, randomized polynomial time algorithm, semidefinite optimization problems, MAX 2-SAT problems, duality relationship, lower bounds, linear programs, semidefinite programming, vertices, chromatic number, MAX CUT, approximation ratio
24	Hans van Maaren, Linda van Norden	Sums of Squares, Satisfiability and Maximum Satisfiability.	SAT	2005	DBLP DOI BibTeX RDF
24	Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich	Certifying Unsatisfiability of Random 2k-SAT Formulas Using Approximation Techniques.	FCT	2003	DBLP DOI BibTeX RDF
23	Joachim Kneis, Daniel Mölle, Stefan Richter 0001, Peter Rossmanith	Algorithms Based on the Treewidth of Sparse Graphs.	WG	2005	DBLP DOI BibTeX RDF
23	Markus Bläser, Bodo Manthey	Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint.	ISAAC	2002	DBLP DOI BibTeX RDF
19	Joshua Brakensiek, Neng Huang, Uri Zwick	Tight approximability of MAX 2-SAT and relatives, under UGC.	SODA	2024	DBLP DOI BibTeX RDF
19	Joshua Brakensiek, Neng Huang, Uri Zwick	Tight approximability of MAX 2-SAT and relatives, under UGC.	CoRR	2023	DBLP DOI BibTeX RDF
19	Hod Wirzberger, Assaf Kalinski, Idan Meirzada, Harel Primack, Yaniv Romano, Chene Tradonsky, Ruti Ben-Shlomi	Lightsolver challenges a leading deep learning solver for Max-2-SAT problems.	CoRR	2023	DBLP DOI BibTeX RDF
19	Yan Ru Pei, Haik Manukian, Massimiliano Di Ventra	Generating Weighted MAX-2-SAT Instances with Frustrated Loops: an RBM Case Study.	J. Mach. Learn. Res.	2020	DBLP BibTeX RDF
19	Yan Ru Pei, Haik Manukian, Massimiliano Di Ventra	Generating Weighted MAX-2-SAT Instances of Tunable Difficulty with Frustrated Loops.	CoRR	2019	DBLP BibTeX RDF
19	Matthew B. Hastings	Local Maxima and Improved Exact Algorithm for MAX-2-SAT.	Chic. J. Theor. Comput. Sci.	2018	DBLP BibTeX RDF
19	Matthew B. Hastings	Local Maxima and Improved Exact Algorithm for MAX-2-SAT.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
19	Matthew B. Hastings	Local Maxima and Improved Exact Algorithm for MAX-2-SAT.	CoRR	2016	DBLP BibTeX RDF
19	Shaowei Cai 0001, Zhong Jie, Kaile Su	An effective variable selection heuristic in SLS for weighted Max-2-SAT.	J. Heuristics	2015	DBLP DOI BibTeX RDF
19	Andrew M. Sutton, Jareth Day, Frank Neumann 0001	A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT.	GECCO	2012	DBLP DOI BibTeX RDF
19	XueLin Xu, Zongsheng Gao, Ke Xu 0001	A tighter upper bound for random MAX 2-SAT.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
19	Toshihide Ibaraki, Takashi Imamichi, Yuichi Koga, Hiroshi Nagamochi, Koji Nonobe, Mutsunori Yagiura	Efficient branch-and-bound algorithms for weighted MAX-2-SAT.	Math. Program.	2011	DBLP DOI BibTeX RDF
19	Daniel Binkele-Raible, Henning Fernau	A new upper bound for Max-2-SAT: A graph-theoretic approach.	J. Discrete Algorithms	2010	DBLP DOI BibTeX RDF
19	Gintaras Palubeckis	A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem.	Appl. Math. Comput.	2009	DBLP DOI BibTeX RDF
19	Gregory Z. Gutin, Eun Jung Kim 0002, Stefan Szeider, Anders Yeo	Solving MAX-2-SAT Above a Tight Lower Bound	CoRR	2009	DBLP BibTeX RDF
19	Daniel Raible 0001, Henning Fernau	A New Upper Bound for Max-2-Sat: A Graph-Theoretic Approach	CoRR	2008	DBLP BibTeX RDF
19	Per Austrin	Balanced Max 2-Sat might not be the hardest.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
19	Haiou Shen, Hantao Zhang 0001	Study of Lower Bound Functions for MAX-2-SAT.	AAAI	2004	DBLP BibTeX RDF
19	Monaldo Mastrolilli, Luca Maria Gambardella	MAX-2-SAT: How Good Is Tabu Search in the Worst-Case?	AAAI	2004	DBLP BibTeX RDF
19	Haiou Shen, Hantao Zhang 0001	Improving Exact Algorithms for MAX-2-SAT.	AI&M	2004	DBLP BibTeX RDF
19	Haiou Shen, Hantao Zhang 0001	An Empirical Study of MAX-2-SAT Phase Transitions.	Electron. Notes Discret. Math.	2003	DBLP DOI BibTeX RDF
19	Edward A. Hirsch	A New Algorithm for MAX-2-SAT.	STACS	2000	DBLP DOI BibTeX RDF
19	Edward A. Hirsch	A New Algorithm for MAX-2-SAT	Electron. Colloquium Comput. Complex.	1999	DBLP BibTeX RDF
19	Joseph Cheriyan, William H. Cunningham, Levent Tunçel, Yaoguang Wang	A linear programming and rounding approach to max 2-sat.	Cliques, Coloring, and Satisfiability	1993	DBLP DOI BibTeX RDF
18	David R. Karger, Rajeev Motwani 0001, Madhu Sudan 0001	Approximate Graph Coloring by Semidefinite Programming.	J. ACM	1998	DBLP DOI BibTeX RDF	approximation algorithms, NP-completeness, randomized algorithms, graph coloring, chromatic number
12	Dániel Marx, Igor Razgon	Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem.	ESA	2009	DBLP DOI BibTeX RDF
12	Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe	The Power of Quantum Systems on a Line.	FOCS	2007	DBLP DOI BibTeX RDF