Approximation Algorithms

Maximizing Non-monotone Submodular Functions under Matroid and Knapsack Constraints

  • Viswanath Nagarajan
  • Vahab S. Mirrokni
  • Maxim Sviridenko
  • Jon Lee
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. Unlike submodular minimization, submodular maximization is NP-hard. In this paper, we give the first constant-factor approximation algorithm for maximizing any … Read more

    Lattice-based Algorithms for Number Partitioning in the Hard Phase

  • Bala Krishnamoorthy
  • Nathan Moyer
  • William Webb
    • Categories Approximation Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    The number partitioning problem (NPP) is to divide n numbers a_1,…,a_n into two disjoint subsets such that the difference between the two subset sums – the discrepancy, D, is minimized. In the balanced version of NPP (BalNPP), the subsets must have the same cardinality. With $a_j$s chosen uniformly from $[1,R]$, R > 2^n gives the … Read more

    A Linear Programming Approach for the Least-Squares Protein Morphing Problem

  • Mihai Anitescu
  • Sanghyun Park
    • Categories Approximation Algorithms, Basic Sciences Applications, Linear Programming Tags , , , ,

    This work addresses the computation of free-energy di fferences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morph- ing procedure, we employ permutations of atoms; we transform atom n in the source conformation into atom \sigma(n) in the target conformation rather than directly transforming atom … Read more

    An FPTAS for Minimizing the Product of Two Non-negative Linear Cost Functions

  • Latife Genc-Kaya
  • Vineet Goyal
  • R. Ravi
    • Categories Approximation Algorithms, Quadratic Programming Tags ,

    We consider a quadratic programming (QP) problem ($\Pi$) of the form $\min x^T C x$ subject to $Ax \ge b$ where $C\in {\mathbb R}^{n\mbox{\tiny\texttimes} n}_+, rank(C)=1$ and $A\in {\mathbb R}^{m\mbox{\tiny\texttimes} n}, b\in {\mathbb R}^m$. We present an FPTAS for this problem by reformulating the QP ($\Pi$) as a parametrized LP and “rounding” the optimal solution. … Read more

    A novel particle swarm optimizer hybridized with extremal optimization

  • Min-Rong Chen
    • Categories Approximation Algorithms, Global Optimization

    Particle swarm optimization (PSO) has received increasing interest from the optimization community due to its simplicity in implementation and its inexpensive computational overhead. However, PSO has premature convergence, especially in complex multimodal functions. Extremal Optimization (EO) is a recently developed local-search heuristic method and has been successfully applied to a wide variety of hard optimization … Read more

    On-line Service Scheduling

  • Bo Chen
  • Wenxun Xing
  • Zhenbo Wang
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    This paper is concerned with a scheduling problem that occurs in service systems, where customers are classified as `ordinary’ and `special’. Ordinary customers can be served on any service facility, while special customers can be served only on the flexible service facilities. Customers arrive dynamically over time and their needs become known upon arrival. We … Read more

    Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems

  • Dongdong Ge
  • Yinyu Ye
  • Shuzhong Zhang
  • Simai He
  • Zizhuo Wang
    • Categories Applications - OR and Management Sciences, Approximation Algorithms

    This paper presents a general technique to develop approximation algorithms for allocation problems with integral assignment constraints. The core of the method is a randomized dependent rounding scheme, called geometric rounding, which yields termwise rounding ratios (in expectation), while emphasizing the strong correlation between events. We further explore the intrinsic geometric structure and general theoretical … Read more

    MOST – Multiple Objective Spanning Trees Repository Project

  • Pedro Cardoso
  • Mário Jesus
  • Alberto Marquez
    • Categories Approximation Algorithms, Multi-Criteria Optimization, Network Optimization Tags ,

    This article presents the Multiple Objective Spanning Trees repository – MOST – Project. As the name suggests, the MOST Project intends to maintain a repository of tests for the MOST related problems, mainly addressing real-life situations. MOST is motivated by the scarcity of repositories for the problems in the referred field. This entails difficulty in … Read more

    A CONSTRUCTIVE HEURISTIC FOR THE INTEGRATED INVENTORY-DISTRIBUTION PROBLEM

  • T. F. Abdelmaguid
  • Maged M. Dessouky
  • Fernando Ordóñez
    • Categories Approximation Algorithms, Supply Chain Management Tags , ,

    We study the integrated inventory distribution problem which is concerned with multiperiod inventory holding, backlogging, and vehicle routing decisions for a set of customers who receive units of a single item from a depot with infinite supply. We consider an environment in which the demand at each customer is deterministic and relatively small compared to … Read more

    On linear infeasibility arising in intensity-modulated radiation therapy inverse planning

  • Adi Ben-Israel
  • Yair Censor
  • James M. Galvin
  • Ying Xiao
    • Categories Applications - Science and Engineering, Approximation Algorithms Tags , , , , ,

    Intensity–modulated radiation therapy (IMRT) gives rise to systems of linear inequalities, representing the effects of radiation on the irradiated body. These systems are often infeasible, in which case one settles for an approximate solution, such as an {a,ß}–relaxation, meaning that no more than a percent of the inequalities are violated by no more than ß … Read more