The Minimum Satisfiability Problem
From MaRDI portal
Publication:4296521
DOI10.1137/S0895480191220836zbMath0806.68060MaRDI QIDQ4296521
Rajeev Kohli, Prakash Mirchandani, Ramesh Krishnamurti
Publication date: 13 February 1995
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Related Items
Computing the Ehrhart polynomial of a convex lattice polytope, Single machine scheduling problems with uncertain parameters and the OWA criterion, A simplified NP-complete MAXSAT problem, Lower and Upper Bounds for Random Mimimum Satisfiability Problem, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, On approximation algorithms for the minimum satisfiability problem, On dependent randomized rounding algorithms, A primal-dual approximation algorithm for \textsc{minsat}, Classes of linear programs solvable by coordinate-wise minimization, On the intractability landscape of digraph intersection representations, Minimal sets on propositional formulae. Problems and reductions, Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case, Revisiting maximum satisfiability and related problems in data streams, Robust optimization with belief functions, On the Minimum Hitting Set of Bundles Problem, Revisiting maximum satisfiability and related problems in data streams, Average performance of greedy heuristics for the integer knapsack problem., Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion, Combinatorial optimization problems with uncertain costs and the OWA criterion, A non-clausal tableau calculus for \textsc{MinSat}, Optimizing with minimum satisfiability, Subset-conjunctive rules for breast cancer diagnosis, Risk-averse single machine scheduling: complexity and approximation, The computational complexity of the pooling problem, Stabilizing network bargaining games by blocking players, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, On reoptimizing multi-class classifiers, Quantum computation techniques for gauging reliability of interval and fuzzy data, Voting on multi-issue domains with conditionally lexicographic preferences, On the minimum hitting set of bundles problem, On dependent randomized rounding algorithms, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
