Approximating Oracle Machines for Combinatorial Optimization

DOI10.1137/0804007MaRDI QIDQ4294748zbMATH OpenOpenAlexFDO

Authors Shmuel Onn

Publication date 12 January 1995

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/71fbf246225153412a5d115546c4ab633f8eee8f

zbMATH Keywords

combinatorial optimizationcones-of-matrices cutting operatororacle Turing machinerational polytopesseparation problem

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 4100502
• On the Complexity of a Cutting Plane Algorithm for Solving Combinatorial Linear Programs
• A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball
• A simple method for convex optimization in the oracle model
• The complexity of approximating a nonlinear program

Cited in

(4)

• A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball
• Computations with oracles: Generalized selection
• scientific article; zbMATH DE number 4100502 (Why is no real title available?)
• Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning

This page was built for publication: Approximating Oracle Machines for Combinatorial Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4294748)