1992 · 215 citations · 29 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDiscrete MathematicsOptimizationApproximation AlgorithmsCombinatorial OptimizationDiscrete OptimizationInteger ProgrammingLinear ProgrammingOptimization TheoryApproximation ComplexityInteger Linear ProgrammingInteger Programming RelaxationsLinear Programming RelaxationsPackingRandomized Approximation AlgorithmsRandomized Packing Algorithmsε-Approximations
We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint violation, the ε-approximation problem for many problems of this type is itself NP-hard. Our methods provide polynomial-time ε-approximations while attempting to minimize the packing constraint violation.
29
Classification and Regression Trees.
John Van Ryzin, Leo Breiman, Jerome H. Friedman et al. · Journal of the American Statistical Association · 1986 · 21K citations
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · COMBINATORICA · 1984 · 4.8K citations
A Greedy Heuristic for the Set-Covering Problem
Vašek Chvátal · Mathematics of Operations Research · 1979 · 2.6K citations