Approximation Algorithms

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

    On the Robust Knapsack Problem

  • Michele Monaci
  • Ulrich Pferschy
    • Categories 0-1 Programming, Approximation Algorithms, Robust Optimization Tags , ,

    We consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value is bounded by a constant. We analyze the worsening of the optimal solution … Read more

    On implementation of local search and genetic algorithm techniques for some combinatorial optimization problems

  • Anton Bondarenko
    • Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics Tags , , , , ,

    In this paper we propose the approach to solving several combinatorial optimization problems using local search and genetic algorithm techniques. Initially this approach was developed in purpose to overcome some difficulties inhibiting the application of above-mentioned techniques to the problems of the Questionnaire Theory. But when the algorithms were developed it became clear that them … Read more

    Job-Shop Scheduling in a Body Shop

  • Joachim Schauer
  • Cornelius Schwarz
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more

    Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations

  • Yun-Bin Zhao
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    Matrix rank minimization problems are gaining a plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization … Read more

    CONVEX HULL RELAXATION (CHR) FOR CONVEX AND NONCONVEX MINLP PROBLEMS WITH LINEAR CONSTRAINTS

  • Aykut Ahlatçıoğlu
  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Constrained Nonlinear Optimization

    The behavior of enumeration-based programs for solving MINLPs depends at least in part on the quality of the bounds on the optimal value and of the feasible solutions found. We consider MINLP problems with linear constraints. The convex hull relaxation (CHR) is a special case of the primal relaxation (Guignard 1994, 2007) that is very … Read more

    A new, solvable, primal relaxation for convex nonlinear integer programming problems

  • Monique Guignard
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Convex Optimization Tags , , ,

    The paper describes a new primal relaxation (PR) for computing bounds on nonlinear integer programming (NLIP) problems. It is a natural extension to NLIP problems of the geometric interpretation of Lagrangean relaxation presented by Geoffrion (1974) for linear problems, and it is based on the same assumption that some constraints are complicating and are treated … Read more

    Combining QCR and CHR for Convex Quadratic MINLP Problems with Linear Constraints

  • Aykut Ahlatçıoğlu
  • Monique Guignard
  • Michael Bussieck
  • Mustafa Esen
  • Jan Jagla
  • Alexander Meeraus
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Semi-definite Programming Tags , , , , , , ,

    The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more

    A Feasible method for Optimization with Orthogonality Constraints

  • Zaiwen Wen
  • Wotao Yin
    • Categories Approximation Algorithms, Nonlinear Optimization Tags , , , , , , , , , ,

    Minimization with orthogonality constraints (e.g., $X^\top X = I$) and/or spherical constraints (e.g., $\|x\|_2 = 1$) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. … Read more

    Burer’s Key Assumption for Semidefinite and Doubly Nonnegative Relaxations

  • Florian Jarre
    • Categories Approximation Algorithms, Quadratic Programming, Semi-definite Programming Tags , ,

    Burer has shown that completely positive relaxations of nonconvex quadratic programs with nonnegative and binary variables are exact when the binary variables satisfy a so-called key assumption. Here we show that introducing binary variables to obtain an equivalent problem that satisfies the key assumption will not improve the semidefinite relaxation, and only marginally improve the … Read more