approximation algorithms

Fully Polynomial Time (Sigma,Pi)-Approximation Schemes for Continuous Nonlinear Newsvendor and Continuous Stochastic Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , , , , ,

    We study the continuous newsvendor problem (i.e. a newsvendor problem concerning goods of a non-discrete nature, such as fresh fruit juice) and a class of stochastic dynamic programs with several application areas, such as inventory control of a continuous good, economics, and supply chain management. The class is characterized by continuous state and action spaces, … Read more

    A Tractable Approach for designing Piecewise Affine Policies in Two-stage Adjustable Robust Optimization

  • Aharon Ben-Tal
  • Omar El Housni
  • Vineet Goyal
    • Categories Robust Optimization Tags , ,

    We consider the problem of designing piecewise affine policies for two-stage adjustable robust linear optimization problems under right-hand side uncertainty. It is well known that a piecewise affine policy is optimal although the number of pieces can be exponentially large. A significant challenge in designing a practical piecewise affine policy is constructing good pieces of … Read more

    A 2-approximation algorithm for the minimum knapsack problem with a forcing graph

  • Shinji Mizuno
  • Yotaro Takazawa
    • Categories Approximation Algorithms Tags , , ,

    Carnes and Shmoys (2015) presented a 2-approximation algorithm for the minimum knapsack problem. We extend their algorithm to the minimum knapsack problem with a forcing graph (MKPFG), which has a forcing constraint for each edge in the graph. The forcing constraint means that at least one item (vertex) of the edge must be packed in … Read more

    Fully Polynomial Time hBcApproximation Schemes for Continuous Stochastic Convex Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , ,

    We develop fully polynomial time $(\Sigma,\Pi)$-approximation schemes for stochastic dynamic programs with continuous state and action spaces, when the single-period cost functions are convex Lipschitz-continuous functions that are accessed via value oracle calls. That is, for every given additive error parameter $\Sigma>0$ and multiplicative error factor $\Pi=1+\epsilon>1$, the scheme returns a feasible solution whose value … Read more

    Provably Near-Optimal Approximation Schemes for Implicit Stochastic and for Sample-Based Dynamic Programs

  • Nir Halman
    • Categories Dynamic Programming Tags , , ,

    In this paper we address two models of non-deterministic discrete-time finite-horizon dynamic programs (DPs): implicit stochastic DPs – the information about the random events is given by value oracles to their CDFs; and sample-based DPs – the information about the random events is deduced via samples. In both models the single period cost functions are … Read more

    Partially Adaptive Stochastic Optimization for Electric Power Generation Expansion Planning

  • Shabbir Ahmed
  • Xu Andy Sun
  • Jikai Zou
    • Categories Stochastic Programming Tags , ,

    Electric Power Generation Expansion Planning (GEP) is the problem of determining an optimal construction and generation plan of both new and existing electric power plants to meet future electricity demand. We consider a stochastic optimization approach for this capacity expansion problem under demand and fuel price uncertainty. In a two-stage stochastic optimization model for GEP, … Read more

    Approximating the Minimum Hub Cover Problem on Planar Graphs

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Hasan M. Jamil
  • Belma Yelbay
    • Categories Applications - Science and Engineering, Approximation Algorithms Tags , , , ,

    We study an approximation algorithm with a performance guarantee to solve a new NP-hard optimization problem on planar graphs. The problem, which is referred to as the minimum hub cover problem, has recently been introduced to the literature to improve query processing over large graph databases. Planar graphs also arise in various graph query processing … Read more

    Approximation algorithms for the Transportation Problem with Market Choice and related models

  • Karen I. Aardal
  • Pierre Le Bodic
    • Categories Approximation Algorithms Tags , ,

    Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them. We give polynomial-time reductions from this problem and variants to the (un)capacitated … Read more

    Reclaimer Scheduling: Complexity and Algorithms

  • Enrico Angelelli
  • Thomas Kalinowski
  • Martin Savelsbergh
  • Reena Kapoor
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor … Read more

    Incremental Network Design with Maximum Flows

  • Thomas Kalinowski
  • Dmytro Matsypura
  • Martin Savelsbergh
    • Categories Approximation Algorithms, Network Optimization Tags , ,

    We study an incremental network design problem, where in each time period of the planning horizon an arc can be added to the network and a maximum flow problem is solved, and where the objective is to maximize the cumulative flow over the entire planning horizon. After presenting two mixed integer programming (MIP) formulations for … Read more