Stephen A. Bloch
Abstract
Many of the "n2-hard" problems described by Gajentaan and Overmars can be solved using limited nondeterminism or other sharply-bounded quantifiers. Thus we suggest that problems are not among the hardest problems solvable in quadratic time
- [1] S. A. Bloch, J. F. Buss, J. Goldsmith, "Sharply Bounded Quantifiers within P," technical report CS94-21. University of Waterloo, 1994.Google Scholar
- [2] S. A. Bloch, J. Goldsmith, "Sharply Bounded Alternation within P," technical report 92-04, University of Manitoba, 1992.Google Scholar
- [3] J. F. Buss, J. Goldsmith, "Nondeterminism within P," SIAM J. Computing 22 (1993) 560-572. Google ScholarDigital Library
- [4] A. Gajentaan, M. H. Overmars, "n2-Hard Problems in Computational Geometry," techical report RUU_CS-93-15, Utrecht Univ., 1993.Google Scholar
- [5] J. O'Rourke, "Computational Geometry Column 22," SIGACT News 25,1 (March 1994) 31-33. Google ScholarDigital Library
- [6] C. P. Schnorr, "Satisfiability is Quasilinear Complete in NQL," J. Assoc. Comput. Mach. 25 (1978) 136-145. Google ScholarDigital Library
Index Terms
- How hard are n2-hard problems?
Recommendations
Solving Hard Mixed-Integer Programming Problems with Xpress-MP: A MIPLIB 2003 Case Study
Despite the fact that no polynomial-time algorithm is known for solving mixed-integer programming (MIP) problems, there has been remarkable success in recent years in solving a wide range of difficult MIPs. In this paper, we take a look at some of the ...
LP relaxations of some NP-hard problems are as hard as any LP
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsWe show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems is as hard as solving the general LP problem. Precisely, the general LP can be reduced in linear time to the LP relaxation of each of ...
Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
<P>It is well-known that many instances of the 0-1 knapsack problem can be effectively solved to optimality also for very large values of n the number of binary variables, while other instances cannot be solved for n equal to only a few hundreds. We ...
Comments