Algorithmic problems on convex sets
Many problems in mathematical programming can be formulated as problems on convex sets or convex bodies. Six kinds of problems are particularly important:[1]: Sec.2 optimization, violation, validity, separation, membership and emptiness. Each of these problems has a strong (exact) variant, and a weak (approximate) variant.
Strong variants
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. This template was placed by Erel Segal (talk · contribs). If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Erel Segal (talk | contribs) 14 months ago. (Update timer) |
Weak variants
References
- ^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419