{
  "id": "2109.10076",
  "version": "v1",
  "published": "2021-09-21T10:28:56.000Z",
  "updated": "2021-09-21T10:28:56.000Z",
  "title": "An Approximation Algorithm for a General Class of Multi-Parametric Optimization Problems",
  "authors": [
    "Stephan Helfrich",
    "Arne Herzel",
    "Stefan Ruzika",
    "Clemens Thielen"
  ],
  "categories": [
    "math.OC",
    "cs.DS"
  ],
  "abstract": "In a widely studied class of multi-parametric optimization problems, the objective value of each solution is an affine function of real-valued parameters. For many important multi-parametric optimization problems, an optimal solutions set with minimum cardinality can contain super-polynomially many solutions. Consequently, any exact algorithm for such problems must output a super-polynomial number of solutions. We propose an approximation algorithm that is applicable to a general class of multi-parametric optimization problems and outputs a number of solutions that is bounded polynomially in the instance size and the inverse of the approximation guarantee. This method lifts approximation algorithms for non-parametric optimization problems to their parametric formulations, providing an approximation guarantee that is arbitrarily close to the approximation guarantee for the non-parametric problem. If the non-parametric problem can be solved exactly in polynomial time or if an FPTAS is available, the method yields an FPTAS. We discuss implications to important multi-parametric combinatorial optimizations problems. Remarkably, we obtain a $(\\frac{3}{2} + \\varepsilon)$-approximation algorithm for the multi-parametric metric travelling salesman problem, whereas the non-parametric version is known to be APX-complete. Furthermore, we show that the cardinality of a minimal size approximation set is in general not $\\ell$-approximable for any natural number $\\ell$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-09-21T10:28:56.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "approximation algorithm",
      "general class",
      "approximation guarantee",
      "important multi-parametric combinatorial optimizations problems",
      "important multi-parametric optimization problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}