Convex Discrete Optimization

Details Convex Discrete Optimization Convex Discrete Optimization

2007-03-20

arxiv.org/abs/math/0703575v1

Encyclopedia of Optimization 2009: 513-550

Mathematics

Optimization and Control

Scientific paper

We develop an algorithmic theory of convex optimization over discrete sets. Using a combination of algebraic and geometric tools we are able to provide polynomial time algorithms for solving broad classes of convex combinatorial optimization problems and convex integer programming problems in variable dimension. We discuss some of the many applications of this theory including to quadratic programming, matroids, bin packing and cutting-stock problems, vector partitioning and clustering, multiway transportation problems, and privacy and confidential statistical data disclosure. Highlights of our work include a strongly polynomial time algorithm for convex and linear combinatorial optimization over any family presented by a membership oracle when the underlying polytope has few edge-directions; a new theory of so-termed n-fold integer programming, yielding polynomial time solution of important and natural classes of convex and linear integer programming problems in variable dimension; and a complete complexity classification of high dimensional transportation problems, with practical applications to fundamental problems in privacy and confidential statistical data disclosure.

Affiliated with

Also associated with

No associations

Rating

Convex Discrete Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convex Discrete Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convex Discrete Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-123448