Approximation Algorithms

Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional action and scalar state

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

    We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problems finds applications in the area of optimal planning under uncertainty, and can be thought of as … Read more

    Disruption Recovery at Airports: Integer Programming Formulations and Polynomial time algorithms

  • Prabhu Manyem
    • Categories 0-1 Programming, Airline Optimization, Approximation Algorithms Tags , , , ,

    We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground … Read more

    Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Kilian Schindler
  • Wolfram Wiesemann
    • Categories Approximation Algorithms, Data-Mining, Linear, Cone and Semidefinite Programming Tags , , ,

    Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer … Read more

    A Novel Approach for Solving Convex Problems with Cardinality Constraints

  • Goran Banjac
  • Paul J. Goulart
    • Categories Approximation Algorithms Tags , , , ,

    In this paper we consider the problem of minimizing a convex differentiable function subject to sparsity constraints. Such constraints are non-convex and the resulting optimization problem is known to be hard to solve. We propose a novel generalization of this problem and demonstrate that it is equivalent to the original sparsity-constrained problem if a certain … Read more

    An Augmented Lagrangian Proximal Alternating Method for Sparse Discrete Optimization Problems

  • Xiaoliang Song
  • Yue Teng
  • Li Yang
  • Bo Yu
    • Categories Approximation Algorithms, Constrained Nonlinear Optimization, Finance and Economics

    In this paper, an augmented Lagrangian proximal alternating (ALPA) method is proposed for two class of large-scale sparse discrete constrained optimization problems in which a sequence of augmented Lagrangian subproblems are solved by utilizing proximal alternating linearized minimization framework and sparse projection techniques. Under the Mangasarian-Fromovitz and the basic constraint qualification, we show that any … Read more

    Locality sensitive heuristics for solving the Data Mule Routing Problem

  • Lucia Drummond
  • Luiz Satoru Ochi
  • P.H. González
  • Philippe Michelon
  • P.L.A Munhoz
  • U.S. Souza
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Telecommunications Tags , , , ,

    A usual way to collect data in a Wireless Sensor Network (WSN) is by the support of a special agent, called data mule, that moves between sensor nodes and performs all communication between them. In this work, the focus is on the construction of the route that the data mule must follow to serve all … Read more

    An approximation algorithm for the partial covering 0-1 integer program

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

    The partial covering 0-1 integer program (PCIP) is a relaxed problem of the covering 0-1 integer program (CIP) such that some fixed number of constraints may not be satisfied. This type of relaxation is also discussed in the partial set multi-cover problem (PSMCP) and the partial set cover problem (PSCP). In this paper, we propose … Read more

    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

    Linear-time approximation algorithms for minimum subset sum and subset sum

  • Liliana Grigoriu
    • Categories Approximation Algorithms

    We present a linear-time approximation algorithm for minimum subset sum, which has better worst-case approximation factor (6/5) than previous linear-time algorithms for this problem. We also present a generalization of the scheme used to derive the algorithm, which can be used to obtain algorithms with approximation ratios of (k+1)/k. In addition, we present a family … Read more

    Decomposition-Based Approximation Algorithms for the One-Warehouse Multi-Retailer Problem with Concave Batch Order Costs

  • Maged M. Dessouky
  • Weihong Hu
  • Alejandro Toriello
  • Zhuoting Yu
    • Categories Approximation Algorithms, Production and Logistics, Supply Chain Management Tags , ,

    We study the one-warehouse multi-retailer (OWMR) problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem … Read more