Главная

David Pritchard

  1. Edge-Colouring Hypergraphs Properly (Covering with Matchings) or Polychromatically (Packing Covers).

    Пт, 10/01/2010 - 15:01 — SomNambul
    Authors: David Pritchard, Thomas Rothvoß
    Subjects: Combinatorics
    Abstract

    Let the chromatic index of a hypergraph be the smallest number of colours
    needed to colour the edges such that similarly-coloured edges are disjoint.
    Likewise, let the cover index be the maximum number of colours so that each
    colour class covers all vertices. Trivially the chromatic index is at least the
    maximum degree, and the cover index is at most the minimum degree. We survey
    some classes of structured hypergraphs and ask how far the trivial bounds are
    from tight. We are motivated by a large amount of recent work in this area for
    geometric settings.

  2. Integrality Gap of the Hypergraphic Relaxation of Steiner Trees: a short proof of a 1.55 upper bound.

    Пнд, 06/14/2010 - 15:01 — SomNambul
    Authors: Deeparnab Chakrabarty, Jochen Koenemann, David Pritchard
    Subjects: Discrete Mathematics
    Abstract

    Recently Byrka, Grandoni, Rothvoss and Sanita (at STOC 2010) gave a
    1.39-approximation for the Steiner tree problem, using a hypergraph-based
    linear programming relaxation. They also upper-bounded its integrality gap by
    1.55. We describe a shorter proof of the same integrality gap bound, by
    applying some of their techniques to a randomized loss-contracting algorithm.

  3. k-Edge-Connectivity: Approximation and LP Relaxation.

    Втр, 04/13/2010 - 15:02 — SomNambul
    Authors: David Pritchard
    Subjects: Discrete Mathematics
    Abstract

    This paper's focus is the following family of problems, denoted k-ECSS, where
    k denotes a positive integer: given a graph (V, E) and costs for each edge,
    find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1
    it is the spanning tree problem which is in P; for every other k it is APX-hard
    and has a 2-approximation.

  4. Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes).

    Втр, 02/23/2010 - 16:02 — SomNambul
    Authors: Prahladh Harsha, David Pritchard, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, Gwen Spencer
    Subjects: Computational Complexity
    Abstract

    These are the lecture notes for the DIMACS Tutorial "Limits of Approximation
    Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building,
    Rutgers University on 20-21 July, 2009. This tutorial was jointly sponsored by
    the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus
    on Algorithmic Foundations of the Internet, and the Center for Computational
    Intractability with support from the National Security Agency and the National
    Science Foundation.

  5. Approximability of Sparse Integer Programs.

    Ср, 02/10/2010 - 16:01 — SomNambul
    Authors: Deeparnab Chakrabarty, David Pritchard
    Subjects: Data Structures and Algorithms
    Abstract

    The main focus of this paper is a pair of new approximation algorithms for
    certain integer programs. First, for covering integer programs {min cx: Ax >=
    b, 0 <= x <= d} where A has at most k nonzeroes per row, we give a
    k-approximation algorithm. (We assume A, b, c, d are nonnegative.) For any k >=
    2 and eps>0, if P != NP this ratio cannot be improved to k-1-eps, and under the
    unique games conjecture this ratio cannot be improved to k-eps.

  6. Hypergraphic LP Relaxations for Steiner Trees.

    Пнд, 10/05/2009 - 20:24 — SomNambul
    Authors: Deeparnab Chakrabarty, Jochen Koenemann, David Pritchard
    Subjects: Discrete Mathematics
    Abstract

    We investigate the partition LP formulation for Steiner trees and extend the
    technique of uncrossing, usually applied to set systems, to families of
    partitions. Using this technique we further our understanding of LP relaxations
    for the Steiner tree problem. Firstly, we show that basic feasible solutions to
    the partition LP formulation have sparse support.

Math-arch

RSS-материал