Approximation Algorithms

Search-Enhanced Instantaneous Frequency Detection Algorithm: A Preliminary Design

  • Phen Chiak See
    • Categories Approximation Algorithms

    This paper presents a method developed for finding sinusoidal components within a nonlinear non-stationary time-series data using Genetic Algorithm (GA) (a global optimization technique). It is called Search-Enhanced Instantaneous Frequency Detection (SEIFD) algorithm. The GA adaptively define the configuration of the components by simulating the solution finding process as a series of genetic evolutions. The … Read more

    New Improved Penalty Methods for Sparse Reconstruction Based on Difference of Two Norms

  • Yingnan Wang
    • Categories Applications - Science and Engineering, Approximation Algorithms, Nonlinear Systems and Least-Squares Tags , , , , , , , ,

    In this paper, we further establish two types of DC (Difference of Convex functions) programming for $l_0$ sparse reconstruction. Our DC objective functions are specified to the difference of two norms. One is the difference of $l_1$ and $l_{\sigma_q}$ norms (DC $l_1$-$l_{\sigma_q}$ for short) where $l_{\sigma_q}$ is the $l_1$ norm of the $q$-term ($q\geq1$) best … Read more

    New Semidefinite Programming Relaxations for the Linear Ordering and the Traveling Salesman Problem

  • Philipp Hungerländer
    • Categories Approximation Algorithms, Production and Logistics, Semi-definite Programming

    In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her … Read more

    On the Adaptivity Gap in Two-stage Robust Linear Optimization under Uncertain Constraints

  • Pranjal Awasthi
  • Vineet Goyal
  • Brian Lu
    • Categories Approximation Algorithms, Robust Optimization

    In this paper, we study the performance of static solutions in two-stage adjustable robust packing linear optimization problem with uncertain constraint coefficients. Such problems arise in many important applications such as revenue management and resource allocation problems where demand requests have uncertain resource requirements. The goal is to find a two-stage solution that maximizes the … 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 of Knapsack Problems with Conflict and Forcing Graphs

  • Ulrich Pferschy
  • Joachim Schauer
    • Categories 0-1 Programming, Approximation Algorithms, Graphs and Matroids

    We study the classical 0-1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be … Read more

    A PTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics

  • T-H. Hubert Chan
  • Shaofeng H.-C. Jiang
    • Categories Approximation Algorithms Tags , , ,

    We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion … 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

    Approximating Convex Functions By Non-Convex Oracles Under The Relative Noise Model

  • Nir Halman
    • Categories Approximation Algorithms Tags ,

    We study succinct approximation of functions that have noisy oracle access. Namely, construction of a succinct representation of a function, given oracle access to an L-approximation of the function, rather than to the function itself. Specifically, we consider the question of the succinct representation of an approximation of a convex function v that cannot be … Read more