Главная

Michel X. Goemans

  1. Symmetric Submodular Function Minimization Under Hereditary Family Constraints.

    Ср, 07/14/2010 - 15:02 — SomNambul
    Authors: Michel X. Goemans, José A. Soto
    Subjects: Data Structures and Algorithms
    Abstract

    We present an efficient algorithm to find non-empty minimizers of a symmetric
    submodular function over any family of sets closed under inclusion. This for
    example includes families defined by a cardinality constraint, a knapsack
    constraint, a matroid independence constraint, or any combination of such
    constraints. Our algorithm make $O(n^3)$ oracle calls to the submodular
    function where $n$ is the cardinality of the ground set.

  2. Combining Approximation Algorithms for the Prize-Collecting TSP.

    Втр, 10/06/2009 - 17:01 — SomNambul
    Authors: Michel X. Goemans
    Subjects: Data Structures and Algorithms
    Abstract

    We present a 1.91457-approximation algorithm for the prize-collecting
    travelling salesman problem. This is obtained by combining a randomized variant
    of a rounding algorithm of Bienstock et al. and a primal-dual algorithm of
    Goemans and Williamson.

  3. A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem.

    Пнд, 09/07/2009 - 22:13 — SomNambul
    Authors: Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain, Mohit Singh
    Subjects: Data Structures and Algorithms
    Abstract

    We present an algorithm for the asymmetric traveling salesman problem on
    instances which satisfy the triangle inequality. Like several existing
    algorithms, it achieves approximation ratio O(log n). Unlike previous
    algorithms, it uses randomized rounding.

Math-arch

RSS-материал