Combinatorial Optimization

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

    A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth

  • Mugurel Ionut Andreica
    • Categories Dynamic Programming, Graphs and Matroids, Network Optimization Tags , , , ,

    In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network’s performance and fault tolerance. The main … Read more

    An Improved Algorithm for the Generalized Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , ,

    In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … Read more

    New Turnpike Theorems for the Unbounded Knapsack Problem

  • Ping H. Huang
  • Thomas L. Morin
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bang-for-buck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce … Read more

    Nonlinear Optimization over a Weighted Independence System

  • Shmuel Onn
  • Robert Weismantel
  • Jon Lee
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , ,

    We consider the problem of optimizing a nonlinear objective function over a weighted independence system presented by a linear-optimization oracle. We provide a polynomial-time algorithm that determines an r-best solution for nonlinear functions of the total weight of an independent set, where r is a constant that depends on certain Frobenius numbers of the individual … Read more

    Parimutuel Betting on Permutations

  • Shipra Agrawal
  • Yinyu Ye
  • Zizhuo Wang
    • Categories Combinatorial Optimization, Convex Optimization, Game Theory Tags , , , ,

    We focus on a permutation betting market under parimutuel call auction model where traders bet on the final ranking of n candidates. We present a Proportional Betting mechanism for this market. Our mechanism allows the traders to bet on any subset of the n x n ‘candidate-rank’ pairs, and rewards them proportionally to the number … 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

    Copositive programming motivated bounds on the stability and the chromatic numbers

  • Igor Dukanovic
  • Franz Rendl
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the … Read more

    Maximizing a Class of Submodular Utility Functions

  • Shabbir Ahmed
  • Alper Atamturk
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , ,

    Given a finite ground set N and a value vector a in R^N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S)= f (sum_{i in S} a_i), S subseteq N, where f is a strictly concave, increasing, differentiable function. This function appears frequently in combinatorial optimization problems when … 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