approximation algorithm

The convergence rate of the Sandwiching algorithm for convex bounded multiobjective optimization

  • Ina Lammel
  • Karl-Heinz Küfer
    • Categories Convex Optimization, Multi-Criteria Optimization Tags , , ,

    Sandwiching algorithms, also known as Benson-type algorithms, approximate the nondominated set of convex bounded multiobjective optimization problems by constructing and iteratively improving polyhedral inner and outer approximations. Using a set-valued metric, an estimate of the approximation quality is determined as the distance between the inner and outer approximation. The convergence of the algorithm is evaluated … Read more

    Computing an approximation of the nondominated set of multi-objective mixed-integer nonlinear optimization problems

  • Leo Warnow
  • Gabriele Eichfelder
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Multi-Criteria Optimization Tags , , , ,

    In practical applications, one often has not only one, but several objectives that need to be optimized simultaneously. What is more, modeling such real world problems usually involves using both, continuous and integer variables. This then results in multi-objective mixed-integer optimization problems, which are in focus of this paper. We present an approximation concept, called … Read more

    Approximation Algorithms for Min-max-min Robust Optimization and K-Adaptability under Objective Uncertainty

  • Jannis Kurtz
    • Categories Approximation Algorithms, Robust Optimization Tags , , ,

    In this work we investigate the min-max-min robust optimization problem and the k-adaptability robust optimization problem for binary problems with uncertain costs. The idea of the first approach is to calculate a set of k feasible solutions which are worst-case optimal if in each possible scenario the best of the k solutions is implemented. It … Read more

    General Polyhedral Approximation of Two-Stage Robust Linear Programming

  • LukasGrunau
  • Tim Niemann
  • Sebastian Stiller
    • Categories Approximation Algorithms, Combinatorial Optimization, Robust Optimization Tags , , , ,

    \(\) We consider two-stage robust linear programs with uncertain righthand side. We develop a General Polyhedral Approximation (GPA), in which the uncertainty set $\mathcal{U}$ is substituted by a finite set of polytopes derived from the vertex set of an arbitrary polytope that dominates $\mathcal{U}$. The union of the polytopes need not contain $\mathcal{U}$. We analyse … Read more

    D-optimal Data Fusion: Exact and Approximation Algorithms

  • Yongchun Li
  • Marcia Fampa
  • Jon Lee
  • Feng Qiu
  • Weijun Xie
    • Categories Combinatorial Optimization, Integer Programming Tags , , , , , , ,

    We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. … Read more

    An approximation algorithm for optimal piecewise linear approximations of bounded variable products

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Katja Kutzer
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Quadratic Programming Tags , , ,

    We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as … Read more

    Approximation algorithm for the two-stage stochastic set multicover problem with simple resource

  • Yotaro Takazawa
    • Categories Approximation Algorithms, Stochastic Programming Tags , , ,

    We study a two-stage, finite-scenarios stochastic version of the set multicover problem, where there is uncertainty about a demand for each element to be covered and the penalty cost is imposed linearly on the shortfall in each demand. This problem is NP-hard and has an application in shift scheduling in crowdsourced delivery services. For this … Read more

    Sequential Competitive Facility Location: Exact and Approximate Algorithms

  • Mingyao Qi
  • Ruiwei Jiang
  • Siqian Shen
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Facility Planning and Design Tags , , , , ,

    We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation … Read more

    A Unified Analysis for Assortment Planning with Marginal Distributions

  • Selin Damla Ahipasaoglu
  • Zeyu Sun
  • Xiaobo Li
    • Categories Applications - OR and Management Sciences Tags , , , , ,

    In this paper, we study assortment planning under the marginal distribution model (MDM), a semiparametric choice model that only requires information about the marginal noise in the utilities of alternatives and does not assume independence of the noise terms. It is already known in the literature that the multinomial logit (MNL) model belongs to the … Read more