Tata Institute of Fundamental Research
An FPTAS for Optimizing a Class of Low-rank Functions Over a Polytope
Seminar
Speaker:
Shashi Mittal (Amazon.com)
Organiser:
Prahladh Harsha
Date:
Monday, 16 Apr 2012, 16:00 to 17:00
Venue:
AG-80
(Scan to add to calendar)
Abstract:
We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of non-linear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity on the objective function. Our technique can also be used to obtain an FPTAS for combinatorial optimization problems with non-linear objective functions, for example when the objective is a product of a fixed number of linear functions. We also show that it is not possible to approximate the minimum of a general concave function over the unit hypercube to within any factor, unless P = NP. We prove this by showing a similar hardness of approximation result for supermodular function minimization, a result that may be of independent interest (this is joint work with Andreas S. Schulz).
[Available from: http://dx.doi.org/10.1007/s10107-011-0511-x ]
| Speaker: | Shashi Mittal (Amazon.com) |
| Organiser: | Prahladh Harsha |
| Date: | Monday, 16 Apr 2012, 16:00 to 17:00 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of non-linear functions of low rank over a polytope. Our approximation scheme relies on constructing an approximate Pareto-optimal front of the linear functions which constitute the given low-rank function. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity on the objective function. Our technique can also be used to obtain an FPTAS for combinatorial optimization problems with non-linear objective functions, for example when the objective is a product of a fixed number of linear functions. We also show that it is not possible to approximate the minimum of a general concave function over the unit hypercube to within any factor, unless P = NP. We prove this by showing a similar hardness of approximation result for supermodular function minimization, a result that may be of independent interest (this is joint work with Andreas S. Schulz).
[Available from: http://dx.doi.org/10.1007/s10107-011-0511-x ]
[Available from: http://dx.doi.org/10.1007/s10107-011-0511-x ]