Michel X. Goemans
Symmetric Submodular Function Minimization Under Hereditary Family Constraints.
Wed, 07/14/2010 - 15:02 — SomNambulAuthors: Michel X. Goemans, José A. Soto
Subjects: Data Structures and Algorithms
AbstractWe 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.Combining Approximation Algorithms for the Prize-Collecting TSP.
Tue, 10/06/2009 - 17:01 — SomNambulAuthors: Michel X. Goemans
Subjects: Data Structures and Algorithms
AbstractWe 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.A Randomized Rounding Algorithm for the Asymmetric Traveling Salesman Problem.
Mon, 09/07/2009 - 22:13 — SomNambulAuthors: Michel X. Goemans, Nicholas J. A. Harvey, Kamal Jain, Mohit Singh
Subjects: Data Structures and Algorithms
AbstractWe 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.
User login
