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)
68Q25: Analysis of algorithms and problem complexity
Related Items
On dependent randomized rounding algorithms, The computational complexity of the pooling problem, Revisiting maximum satisfiability and related problems in data streams, Robust optimization with belief functions, Single machine scheduling problems with uncertain parameters and the OWA criterion, A simplified NP-complete MAXSAT problem, Combinatorial optimization problems with uncertain costs and the OWA criterion, On reoptimizing multi-class classifiers, On the minimum hitting set of bundles problem, On dependent randomized rounding algorithms, Computing the Ehrhart polynomial of a convex lattice polytope, On approximation algorithms for the minimum satisfiability problem, Average performance of greedy heuristics for the integer knapsack problem., Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, Minimal sets on propositional formulae. Problems and reductions, Optimizing with minimum satisfiability, Stabilizing network bargaining games by blocking players, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., 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, A non-clausal tableau calculus for \textsc{MinSat}, Risk-averse single machine scheduling: complexity and approximation, Voting on multi-issue domains with conditionally lexicographic preferences, Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case, Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion, Subset-conjunctive rules for breast cancer diagnosis, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Quantum computation techniques for gauging reliability of interval and fuzzy data, Lower and Upper Bounds for Random Mimimum Satisfiability Problem, On the Minimum Hitting Set of Bundles Problem
