2011 · 49 citations · 11 references
Mathematical ProgrammingComputational Complexity TheoryEngineeringSimple Randomized AlgorithmAlgorithmic Information TheoryRandomized AlgorithmSat SolvingFull DerandomizationComputational ComplexityTime An+oTime ComplexityComputer ScienceDiscrete MathematicsCombinatorial OptimizationSatisfiabilityDeterministic Version
Schoening in 1999 presented a simple randomized algorithm for k-SAT with running time an * poly(n) for a = 2(k-1)/k. We give a deterministic version of this algorithm running in time an+o(n).
11
Approximation Algorithms for NP-Hard Problems
Dorit S. Hochba · ACM SIGACT News · 1997 · 3.1K citations · Full text
Mathematical Programming, Engineering, Performance Guarantee +15