23 citations · 42 across the 17 of their papers we have counts for
4 papers · 1 filter
Generalized Hypergraph Matching via Iterated Packing and Local Ratio
Ojas Parekh, David Pritchard
In -hypergraph matching, we are given a collection of sets of size at most , each with an associated weight, and we seek a maximum-weight subcollection whose sets are pairwis…
On Approximating String Selection Problems with Outliers
Christina Boucher, Gad M. Landau, Avivit Levy +2
Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can…
Approximability of Sparse Integer Programs
David Pritchard, Deeparnab Chakrabarty
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…
A Partition-Based Relaxation For Steiner Trees
Jochen Konemann, David Pritchard, Kunlun Tan
The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G…