A Multi-Exchange Local Search Algorithm for the Capacitated Facility Location Problem

  • Bo Chen
  • Yinyu Ye
  • Jiawei Zhang
    • Categories Approximation Algorithms, Network Optimization Tags , ,

    We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant … Read more

    Complete Search in Continuous Global Optimization and Constraint Satisfaction

  • Arnold Neumaier
    • Categories Global Optimization Theory

    This survey covers the state of the art of techniques for solving general purpose constrained global optimization problems and continuous constraint satisfaction problems, with emphasis on complete techniques that provably find all solutions (if there are finitely many). The core of the material is presented in sufficient detail that the survey may serve as a … Read more

    New criss-cross type algorithms for linear complementarity problems with sufficient matrices

  • Zsolt Csizmadia
  • Tibor Illés
    • Categories Applications - OR and Management Sciences Tags , , ,

    We generalize new criss-cross type algorithms for linear complementarity problems (LCPs) given with sufficient matrices. Most LCP solvers require apriori information about the input matrix. The sufficiency of a matrix is hard to be checked (no polynomial time method is known). Our algorithm is similar to Zhang’s linear programming, and Akkeleº-Balogh-Illés’s criss-cross type algorithm for … Read more

    The Reduced Density Matrix Method for Electronic Structure Calculations and the Role of Three-Index Representability Conditions

  • Bastiaan J. Braams
  • Mituhiro Fukuda
  • Michael L. Overton
  • Jerome K. Percus
  • Zhengji Zhao
    • Categories Basic Sciences Applications, Convex Optimization, Semi-definite Programming Tags

    The variational approach for electronic structure based on the two-body reduced density matrix is studied, incorporating two representability conditions beyond the previously used $P$, $Q$ and $G$ conditions. The additional conditions (called $T1$ and $T2$ here) are implicit in work of R.~M.~Erdahl [Int.\ J.\ Quantum Chem.\ {\bf13}, 697–718 (1978)] and extend the well-known three-index diagonal … Read more

    Stable Matchings for A Generalized Marriage Problem

  • Somdeb Lahiri
    • Categories Finance and Economics, Game Theory Tags , , , ,

    We show that a simple genralization of the Deferred Acceptance Procedure with men proposing due to Gale and Shapley(1962), yeilds outcomes for a generalized marriage problem, which are necessarily stable. We also show, that any outcome of this prcedure is Weakly Pareto Optimal for Men, i.e., there is no other outcome which all men prefer … Read more

    An updated bibliography of GRASP

  • Paola Festa
  • Mauricio G.C. Resende
    • Categories Meta Heuristics Tags , ,

    This document contains references related to GRASP (greedy randomized adaptive search procedure) that have either appeared in the literature or as technical reports. If you are aware of any uncited reference, incorrectly cited reference, or update to a cited reference, please contact Mauricio G. C. Resende at the address given at the end of this … Read more

    On Extracting Maximum Stable Sets in Perfect Graphs Using Lovasz’s Theta Function

  • Xiaofei Fan
  • E. Alper Yildirim
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lov{\’a}sz’s theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a … Read more

    A Grid-Enabled Distributed Branch-and-Bound Algorithm with

  • Clicia Castro
  • Lucia Drummond
  • Eduardo Uchoa
  • José Viterbo
    • Categories Parallel Algorithms Tags , ,

    This work introduces a distributed branch-and-bound algorithm to be run on computational Grids. Grids are often organized in a hierarchical fashion: clusters of processors connected via high-speed links, while the clusters themselves are geographically distant and connected through slower links. Our algorithm does not employ the usual master-worker paradigm and it considers the hierarchical structure … Read more

    GRASP and path-relinking: Recent advances and applications

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , ,

    A greedy randomized adaptive search procedure (GRASP) is a multi-start metaheuristic which applies local search to starting solutions generated by a greedy randomized construction procedure. Until recently, most implementations of GRASP assumed independence of its iterations, thus making no use of memory structures. Path-relinking is an intensification strategy which explores trajectories between elite solutions. Using … Read more

    Automatic Scheduling of Hypermedia Documents with Elastic Times]

  • Maira Medina
  • Celso C. Ribeiro
  • Luiz Fernando Soares
    • Categories 0-1 Programming, Linear Programming, Scheduling Tags , ,

    The problem of automatic scheduling hypermedia documents consists in finding the optimal starting times and durations of objects to be presented, to ensure spatial and temporal consistency of a presentation while respecting limits on shrinking and stretching the ideal duration of each object. The combinatorial nature of the minimization of the number of objects whose … Read more