Shashi Mittal

An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Global Optimization Theory Tags , ,

    We present a fully polynomial time approximation scheme (FPTAS) for optimizing a very general class of nonlinear 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 … Read more

    A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined Into One

  • Shashi Mittal
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Robust Optimization, Scheduling Tags , , ,

    In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the … Read more