Skip to main content
eScholarship
Open Access Publications from the University of California

Approximation Algorithms for Covering Problems

  • Author(s): Koufogiannakis, Christos
  • Advisor(s): Young, Neal E
  • et al.
Abstract

In this thesis we present sequential and distributed approximation algorithms for covering problems.

First, we give a sequential $\ratio$-approximation algorithm for Monotone Covering, a generalization of many fundamental NP-hard covering problems. The approximation ratio $\ratio$ is the maximum number of variables on which any constraint depends. (For example, for vertex cover, $\ratio$ is 2.) The algorithm unifies, generalizes, and improves

many previous algorithms for fundamental covering problems such as Vertex Cover, Set Cover, Facilities Location, and Covering Mixed-Integer Linear Programs with upper bound on the variables.

The algorithm is also a $\ratio$-competitive algorithm for online Monotone Covering, which generalizes online versions of the above-mentioned covering problems as well as many fundamental online paging and caching problems. As such it also generalizes many classical online algorithms, including LRU, FIFO, FWF, Balance, Greedy-Dual, Greedy-Dual Size (a.k.a. Landlord), and algorithms for connection caching, where $\ratio$ is the cache size. It also gives new $\ratio$-competitive algorithms for upgradable variants of these problems, which model choosing the caching strategy and

an appropriate hardware configuration (cache size, CPU, bus, network, etc.).

Then we show distributed versions of the sequential algorithm.

For Weighted Vertex Cover, we give a distributed 2-approximation algorithm taking $O(\log n)$ rounds. The algorithm generalizes to covering mixed integer linear programs (CMIP) with two variables per constraint ($\ratio=2$). For any Monotone Covering problem, we show

a distributed $\ratio$-approximation algorithm taking

$O(\log^2 |\calC|)$ rounds, where $|\calC|$ is the number of constraints.

Last, we extend the distributed algorithms for covering to compute $\ratio$-approximate solutions for Fractional Packing and Maximum Weighted b-Matching in hypergraphs, where $\ratio$ is the maximum number of packing constraints in which a variable appears (for Maximum Weighted b-Matching $\ratio$ is the maximum edge degree --- for graphs $\ratio=2$).

Main Content
Current View