Approximation Algorithms

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

    Sharing Supermodular Costs

  • Andreas S. Schulz
  • Nelson A. Uhan
    • Categories Approximation Algorithms, Game Theory, Graphs and Matroids

    We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations: in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron–a problem that often arises in combinatorial optimization–has supermodular optimal costs. In addition, we examine the computational complexity of the least core … Read more

    Revisiting the Greedy Approach to Submodular Set Function Maximization

  • Pranava R. Goundan
  • Andreas S. Schulz
    • Categories Approximation Algorithms, Graphs and Matroids

    We consider the problem of maximizing a nondecreasing submodular set function over various constraint structures. Specifically, we explore the performance of the greedy algorithm, and a related variant, the locally greedy algorithm in solving submodular function maximization problems. Most classic results on the greedy algorithm and its variant assume the existence of an optimal polynomial-time … Read more

    Approximate Solutions for Deterministic and Stochastic Multi-Dimensional Sequencing

  • B Jothi
  • Sachin Patkar
  • Chandra Poojari
  • Janak Porwal
    • Categories Approximation Algorithms, Scheduling Tags , , , ,

    We investigate the problem of sequencing jobs that have multiple components. Each component of the job needs to be processed independently on a specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose … Read more

    A novel elitist multiobjective optimization algorithm: multiobjective extremal optimization

  • Min-Rong Chen
  • Yong-Zai Lu
    • Categories Approximation Algorithms, Meta Heuristics, Multi-Criteria Optimization

    Recently, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in multiobjective optimization and proposes a new novel elitist multiobjective algorithm, called Multiobjective Extremal Optimization (MOEO). In order to extend EO to solve the multiobjective … Read more