# Your search: "(author:"Young, N" OR author:"Young, Neal" OR author:"Young, Neal E" OR author:"Young, N E" OR author:"Young, NE")"

**1** filter applied

Campus (UC Riverside)

## Type of Work

Article (44) Book (0) Theses (2) Multimedia (0)

## Peer Review

Peer-reviewed only (46)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (0) UC Davis (1) UC Irvine (1) UCLA (2) UC Merced (0) UC Riverside (46) UC San Diego (0) UCSF (0) UC Santa Barbara (0) UC Santa Cruz (0) UC Office of the President (1) Lawrence Berkeley National Laboratory (0) UC Agriculture & Natural Resources (0)

## Department

Bourns College of Engineering (44)

## Journal

## Discipline

## Reuse License

## Scholarly Works (46 results)

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$).

This thesis focuses on approximation and online algorithms for a few different problems.

1) There have been continued improvements in the approximation algorithms for packing and covering problems. Some recent algorithms, including Fastpc, have provable good worst-case running times, but it is not known how they perform in practice compared to the simplex and interior-point algorithms that are widely used to solve these problems. We present an empirical comparison of these algorithms, using our own implementation of Fastpc and CPLEX implementations of simplex and interior-point methods. We use a variety of inputs for this experimental study. We find that Fastpc is slower for small problem instances, but its performance, relative to CPLEX algorithms, improves as the instances get bigger. Our experiments show that for reasonably large inputs Fastpc performs better than the CPLEX algorithms.

2) We give deterministic algorithms for some variants of online file caching by reducing the problems to online covering. The variants considered in this study include one or both of the following features: (i) a rental cost for each slot occupied in the cache, and (ii) zapping a file by paying a cost so that the zapped file does not occupy any space in the cache and does not incur any retrieval cost. The rental cost is motivated by the idea of energy efficient caching where caching systems can save power by turning off slots not being used to store files. Our approach is based on the online covering algorithm by Koufogiannakis and Young. We give deterministic lower bounds for these variants, which are tight within con-

stant factors of the upper bounds for most of the cases. We also give randomized algorithms and lower bounds for the variants with rental cost.

3) We introduce online Huffman coding. In Huffman coding, the symbols are drawn from a probability distribution and revealed one by one, and the goal is to find a minimum cost prefix-code for the symbols. In the online version, the algorithm has to assign a codeword to a symbol when it is revealed for the first time. We propose an online greedy algorithm and show that it is constant-competitive for online Huffman coding. We also show a lower bound of 10/9 on the competitive ratio of any deterministic online algorithm.

^{2}) iterations to compute a (1 + ∈)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ∈). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ∈)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games.