%% For testing acm LaTeX stuff. Took out all the undefined control
%% sequences, so not really the start of our SODA paper
\documentclass{rev_acm_proc_article-sp}
\begin{document}
\title{Strengthening Integrality Gaps for Capacitated Network Design
and Covering Problems}
\numberofauthors{4}
\author{
\alignauthor
Robert D. Carr\titlenote{Sandia National Labs, Albuquerque, NM 87185.
Sandia is a multiprogram laboratory operated by Sandia Corporation, a
Lockheed Martin
Company, for the United States Department of Energy under contract
DE-AC04-94AL85000.
Email: {\tt \{bobcarr@cs.sandia.gov,\\ vjleung@mp.sandia.gov,
caphill@mp.sandia.gov\}}.}
\alignauthor
Lisa K. Fleischer\titlenote{Industrial Engineering and Operations
Research, Columbia University, New York, NY 10027. Part of this
research was done while visiting CORE, Universit\'e catholique de
Louvain, Belgium.
Email: {\tt lisa@ieor.columbia.edu}.}
\alignauthor Vitus J. Leung$^*$
\alignauthor Cynthia A. Phillips$^*$}
\maketitle
\begin{abstract} \small % \baselineskip=10pt
%{\small
A {\em capacitated covering IP} is an integer program of the form
$\min \{cx | Ux \geq d, 0\leq x \leq b, x \in Z^+ \}$, where
all entries of $c$, $U$, and $d$ are nonnegative. Given such
a formulation, the ratio between the optimal integer solution and
the optimal solution to the linear program relaxation can
be as bad as $||d||_\infty$, even when $U$ consists of a single row.
We show that by adding additional inequalities, this ratio can
be improved significantly. In the general case, we show that
the improved ratio is bounded by the maximum number of non-zero
coefficients in a row of $U$, and provide a polynomial-time
approximation algorithm to achieve this bound. This improves
the previous best approximation algorithm which guaranteed
a solution within the maximum row {\em sum} times optimum.
We also show that for particular instances of capacitated
covering problems, including the minimum knapsack problem and the
capacitated network design problem, these additional inequalities
yield even stronger improvements in the IP/LP ratio. For the minimum
knapsack, we show that this improved ratio is at most 2.
This is the first non-trivial IP/LP ratio for this basic problem.
Capacitated network design generalizes the classical network
design problem
by introducing capacities on the edges, whereas previous
work only considers the case when all capacities equal 1.
For capacitated network
design problems, we show that this improved ratio depends on a parameter
of the graph, and we also provide polynomial-time approximation
algorithms to match this bound. This improves on the best previous
$m$-approximation, where $m$ is the number of edges in the
graph.
We also discuss improvements for some other
special capacitated covering problems, including the fixed charge
network flow problem.
Finally, for the capacitated network design problem, we give some
stronger results and algorithms for series parallel graphs and
strengthen these further for outerplanar graphs.
Most of our approximation algorithms rely on solving a single LP.
When the original LP (before adding our strengthening
inequalities) has a polynomial number of constraints, we describe a
combinatorial FPTAS for the
LP with our (exponentially-many)
inequalities added. Our contribution here is to describe an
appropriate separation algorithm to work in the setting of
the FPTAS of Garg and K\"onemann.
For exactly solving the LP using the ellipsoid method, we
describe simpler separation routines.
%}
\end{abstract}
\section{Introduction}
The US government has identified $7$ areas of {\em critical
infrastructure}, sets of services whose functioning is essential for
the current operation of the country. Most of these infrastructures
are physical networks such as telecommunications, water, natural gas,
and transportation. The importance of network design is further evident from
the wealth of literature on the subject~\cite{GKP}.
The research in this paper is motivated
by a capacitated network design problem arising in network security.
However, the tools we have devised to understand this
problem are applicable not only to building networks, but also
to both more specific
problems, such as the minimum knapsack problem, and more general
problems, such as general capacitated covering problems.
The {\em capacitated network design problem} is defined on a
multigraph $G=(V,E)$ with cost vector $c:E\rightarrow R^+$,
capacity vector $u:E\rightarrow R^+$, and symmetric demand matrix
$D\in N^{|V|^2}$, where $D_{ij}$ is the connectivity requirement
between vertices $i$ and $j$. The goal is to select a minimum-cost
subset of edges $F\subset E$ so that the total capacity of any cutset $C$
of $(V,F)$ is at least the maximum demand among all pairs of vertices
that are disconnected in $(V, F\backslash C)$. In this paper,
we also consider the generalization where edge $e$ may be selected up
to $b(e)$ times.
The capacitated network design problem arises as a {\em network
reinforcement
problem}. Here we are given an existing
network, and for each link (edge) in the network, several reinforcement
options. A {\em reinforcement} is a protection level of a particular
strength that can be added to an edge at a certain cost. In addition,
for each pair of vertices in the network, there is a specified level
of protection demanded.
The objective
is to select a minimum-cost set of reinforcements for all the edges
so that an adversary with strength less than the protection level of
a particular pair of vertices
\end{document}