Oblivious Medians via Online Bidding\\ (Extended Abstract)
Marek Chrobak\inst{1}\thanks{Research supported by NSF Grant CCR-0208856.}
Claire Kenyon\inst{2}
John Noga\inst{3}
Neal E. Young\inst{1}
Following Mettu and Plaxton \cite{MetPla00,mettu03}, we study oblivious algorithms for the $k$-medians problem. Such an algorithm produces an incremental sequence of facility sets. We give improved algorithms, including a $(24+\epsilon)$-competitive deterministic polynomial algorithm and a $2e\approx{}5.44$-competitive, randomized, non-polynomial algorithm. Our approach is similar to that of~\cite{LNRW06}, which was done independently. We then consider the competitive ratio with respect to {\em size}. An algorithm is {\em $s$-size-competitive} if, for each $k$, the cost of $F_k$ is at most the minimum cost of any set of $k$ facilities, while the size of $F_k$ is at most $s k$. We present optimally competitive algorithms for this problem. Our proofs reduce oblivious medians to the following online bidding problem: faced with some unknown threshold $T\in\posreals$, an algorithm must submit ``bids'' $b\in\posreals$ until it submits a bid $b\ge T$, paying the sum of its bids. We describe optimally competitive algorithms for online bidding. Some of Our results extend to approximately metric distance functions, oblivious fractional medians, and oblivious bicriteria approximation. When the number of medians takes only two possible values $k$ or $l$, for $k<l$, we show that the optimal cost-competitive ratio is $2-1/l$.
final_latin.tex

\documentclass[runningheads]{llncs}

\input{psfig.sty}
\usepackage{epsfig,picinpar,latexsym,amsmath,amsfonts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\myparagraph}[1]{{\smallskip\noindent{\bf #1}}}
\newcommand{\etal}{\emph{et al.}}
\newcommand{\myif}{{\mbox{\rm\ if \ }}}
\newcommand{\mycase}[1]{\mbox{{\underline{Case #1}}:\/}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% various leters

\newcommand{\hatc}{{\hat c}}
\newcommand{\hatr}{{\hat r}}

\newcommand{\baru}{{\bar u}}
\newcommand{\barx}{{\bar x}}
\newcommand{\bary}{{\bar y}}
\newcommand{\barz}{{\bar z}}
\newcommand{\barr}{{\bar r}}
\newcommand{\barX}{{\bar X}}
\newcommand{\barF}{{\bar F}}
\newcommand{\barY}{{\bar Y}}
\newcommand{\barZ}{{\bar Z}}
\newcommand{\bara}{{\bar a}}
\newcommand{\bard}{{\bar d}}
\newcommand{\barm}{{\bar m}}
\newcommand{\barA}{{\bar A}}
\newcommand{\bargamma}{{\bar \gamma}}

\newcommand{\bfb}{{\bf b}}
\newcommand{\bfr}{{\bf r}}
\newcommand{\bfv}{{\bf v}}
\newcommand{\bfx}{{\bf x}}
\newcommand{\bfy}{{\bf y}}
\newcommand{\bfz}{{\bf z}}
\newcommand{\bfQ}{{\bf Q}}
\newcommand{\bfR}{{\bf R}}
\newcommand{\bfS}{{\bf S}}
\newcommand{\bfT}{{\bf T}}
\newcommand{\bfV}{{\bf V}}

\newcommand{\calA}{{\cal A}}
\newcommand{\calB}{{\cal B}}
\newcommand{\barcalB}{\bar{\cal B}}
\newcommand{\calC}{{\cal C}}
\newcommand{\calD}{{\cal D}}
\newcommand{\calF}{{\cal F}}
\newcommand{\calG}{{\cal G}}
\newcommand{\calH}{{\cal H}}
\newcommand{\calK}{{\cal K}}
\newcommand{\calL}{{\cal L}}
\newcommand{\calM}{{\cal M}}
\newcommand{\calN}{{\cal N}}
\newcommand{\calP}{{\cal P}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calS}{{\cal S}}
\newcommand{\calU}{{\cal U}}
\newcommand{\calX}{{\cal X}}
\newcommand{\calT}{{\cal T}}

\newcommand{\vecS}{{\bar S}}
\newcommand{\vecT}{{\bar T}}
\newcommand{\vecone}{{\bf 1}}

\newcommand{\tildeD}{{\tilde D}}
\newcommand{\tildeC}{{\widetilde C}}
\newcommand{\tildec}{{\tilde c}}

\newcommand{\dotc}{{\dot c}}

\newcommand{\eps}{{\epsilon}}
\newcommand{\assign}{{\,\leftarrow\,}}

\newcommand{\I}{I}

\newcommand{\mathtext}[1]{%
  \\
  \lefteqn{\hspace*{-0.9in}\parbox{\textwidth}{#1}}
  \\
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% various delimiters

\newcommand{\braced}[1]{{ \left\{ #1 \right\} }}
\newcommand{\angled}[1]{{ \left\langle #1 \right\rangle }}
\newcommand{\brackd}[1]{{ \left[ #1 \right] }}
\newcommand{\bigbrackd}[1]{{ \big[ #1 \big] }}
\newcommand{\Bigbrackd}[1]{{ \Big[ #1 \Big] }}
\newcommand{\parend}[1]{{ \left( #1 \right) }}
\newcommand{\barred}[1]{{ \left| #1 \right| }}
\newcommand{\dbarred}[1]{{ \left\| #1 \right\| }}
\newcommand{\ceiling}[1]{{ \left\lceil #1 \right\rceil }}
\newcommand{\floor}[1]{{ \left\lfloor #1 \right\rfloor }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% some math symbols

\newcommand{\set}{\,{\leftarrow}\,}
\newcommand{\cost}{\mbox{\it cost}}
\newcommand{\opt}{\mbox{\it opt}}

\newcommand{\Exp}{\mbox{\rm Exp}}
\newcommand{\Prob}{\mbox{\rm Pr}}
\newcommand{\rank}{{r}}

\newcommand{\trees}{{\calT}}
\newcommand{\weight}{{w}}

\newcommand{\half}{{\frac{1}{2}}}
\newcommand{\threehalves}{{\mbox{$\frac{3}{2}$}}}
\newcommand{\onethird}{{\mbox{$\frac{1}{3}$}}}
\newcommand{\twothirds}{{\mbox{$\frac{2}{3}$}}}
\newcommand{\fivethirds}{{\mbox{$\frac{5}{3}$}}}
\newcommand{\onesixth}{{\mbox{$\frac{1}{6}$}}}

\newcommand{\invd}{{\bard}}
\newcommand{\abs}[1]{{\barred{#1}}}

\newcommand{\integers}{{\mathbb{Z}}}
\newcommand{\reals}{{\mathbb{R}}}
\newcommand{\posreals}{{\mathbb{R}^+}}
\newcommand{\naturals}{{\mathbb{N}}}
\newcommand{\posnaturals}{{\mathbb{N}^+}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\title{Oblivious Medians via Online Bidding\\
                (Extended Abstract)}

\author{
       Marek Chrobak\inst{1}\thanks{Research supported
         by NSF Grant CCR-0208856.}
       \and
       Claire Kenyon\inst{2}
       \and
       John Noga\inst{3}
       \and
       Neal E. Young\inst{1}
     }

\institute{Department of Computer Science,
       University of California, Riverside.
       \and
       Computer Science Department,
       Brown University.
       \and
       Department of Computer Science,
       California State University, Northridge.
        }





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\maketitle

\begin{abstract}
  Following Mettu and Plaxton \cite{MetPla00,mettu03}, we study oblivious
  algorithms for the $k$-medians problem.  Such an algorithm
  produces an incremental sequence of facility sets.
  We give improved algorithms, including a $(24+\epsilon)$-competitive
  deterministic polynomial algorithm and a
  $2e\approx{}5.44$-competitive, randomized, non-polynomial
  algorithm. Our approach is similar to that of~\cite{LNRW06}, which
  was done independently.
  
  We then consider the competitive ratio with respect to {\em size}.
  An algorithm is {\em $s$-size-competitive} if, for each $k$, the
  cost of $F_k$ is at most the minimum cost of any set of $k$
  facilities, while the size of $F_k$ is at most $s k$.  
  We present optimally competitive algorithms for this problem.
  
  Our proofs reduce oblivious medians to the following \emph{online
    bidding} problem: faced with some unknown threshold
  $T\in\posreals$, an algorithm must submit ``bids'' $b\in\posreals$
  until it submits a bid $b\ge T$, paying the sum
  of its bids.  We describe optimally competitive algorithms for
  online bidding.

  Some of Our results extend to
  approximately metric distance functions, oblivious fractional medians,
  and oblivious bicriteria approximation.

  When the number of medians takes only two possible values
  $k$ or $l$, for $k<l$,
  we show that the optimal cost-competitive ratio is $2-1/l$.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\thispagestyle{empty}
%\setcounter{page}{0}
%\newpage

\section{Introduction and summary of results}

%\paragraph{Oblivious medians.}
An instance of the $k$-median problem is specified by a finite set
$\calC$ of customers, a finite set $\calF$ of facilities, and, for
each customer $u$ and  facility $f$, a distance $d_{uf}\ge 0$ from
$u$ to $f$ representing the cost of serving $u$ from $f$.  The cost of a set of
facilities $X\subseteq\calF$ is 
$\cost(X)=\sum_{u\in\calC}d_{uX}$, where
$d_{uX}=\min_{f\in{}X}d_{uf}$.  For a given $k$, 
the \emph{(offline) k-median problem} is to
compute a \emph{$k$-median}, that is,
a set $X\subseteq\calF$ of cardinality $k$ for which 
$\cost(X)=\opt_k$ is
minimum (among all sets of cardinality $k$). 
{\em Metric} $k$-median refers to the case where
 the distance function is { metric} (the shortest $u$-to-$f$ path
has length $d_{uf}$ for each $u$ and $f$).

The $k$-median problem is a well-known NP-hard facility location
problem.   Substantial work has been done
on efficient approximation algorithms that, given $k$, find a set
$F_k$ of $k$ medians of approximately minimum cost
\cite{arya01,ArRaSh03,charikar99a,charikar99b,jain01,jain02,young00kmedians}.  In
particular, for the metric version Arya et al.\ show that, for any $\epsilon > 0$,
a set $F_k$ of cost at most
$(3+\epsilon)\opt_k$ can be found in
polynomial time \cite{arya01}.

{\em Oblivious medians} is an online version of the $k$-median problem
where $k$ is not specified in advance \cite{MetPla00,mettu03}.
Instead, authorizations for additional facilities arrive over time.  A
(possibly randomized) \emph{oblivious algorithm} produces a sequence
$\barF=(F_1,F_2,\ldots,F_n)$ of facility sets which must satisfy
the oblivious constraint 
$F_1\subseteq{}F_2\subseteq\cdots\subseteq{}F_n{}\subseteq\calF$.  In
general, in an oblivious solution, the $F_k$'s cannot all simultaneously
have minimum cost.  The algorithm is said to be {\em
  $c$-cost-competitive}, or to have {\em cost-competitive ratio} of
$c$, if it produces a (possibly random) sequence $\barF$ of sets which
is $c$-cost-competitive, that is, such that for each $k$, the set
$F_k$ has size at most $k$ and (expected) cost at most $c\cdot\opt_k$.
For offline solutions we use the term ``approximate'' instead of
``competitive''.

\smallskip

Mettu and Plaxton~\cite{MetPla00,mettu03} give a $c$-cost-competitive linear time oblivious
algorithm with $c\approx 30$.   Our first contribution is to
improve this ratio.    The problem is difficult both because (1) the solution must be
oblivious, and (2) even the offline problem is NP-hard.    
To study separately the effects of the two difficulties,
we consider both polynomial and non-polynomial
algorithms.

%%%%%%%%%%%%%%%%

\smallskip

\begin{theorem}\label{thm: cost competitive}
  {\rm\bf (a)} Oblivious metric medians has non-polynomial
  deterministic and randomized algorithms that are
  $8$-cost-competitive and $2e$-cost-competitive, respectively.
  {\rm\bf (b)} If (offline) metric $k$-median has a
  polynomial $c$-cost-approximation algorithm, then the
  oblivious problem has polynomial deterministic and
  randomized algorithms that are $8c$-cost-competitive and
  $2ec$-cost-competitive, respectively.
\end{theorem}

As it is known that there is a polynomial
$(3+\eps)$-cost-approximation algorithm for the offline metric medians
\cite{arya01}, Theorem~\ref{thm: cost competitive} implies the
cost-competitive ratios shown in Fig.~\ref{fig: results}.
Theorem~\ref{thm: cost competitive} was recently
and independently discovered by
Lin, Nagarajan, Rajaraman and Williamson~\cite{LNRW06}.
For polynomial algorithms, they improved the result further
using a Lagrangian-multiplier-preserving approximation algorithm
for facility location; they obtained $16$-cost-competitive and randomized $4e$-competitive
polynomial algorithms for metric medians.

%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[t]\small
  \centering
\begin{tabular}[h]{|r|c|c|c|c|c|}\hline
\em problem:
&
\multicolumn{2}{|c|}{\bf cost-competitive metric} 
&
\multicolumn{2}{|c|}{\bf size-competitive}
&{\bf bidding}
\\  \hline
\em time:
&{polynomial} 
&{non-polynomial}
&{polynomial} 
&{non-polynomial}
&polynomial
\\\hline
deterministic     & $24+\eps$     &  $8$ 
& $\mathbf{O(\mbox{\bf log}\, n)}$
& \bf 4
& \bf 4
\\\hline
randomized        & $6e+\eps< 16.31$  &  $2e< 5.44$ 
& $\mathbf{O(\mbox{\bf log}\, n)}$
& $\mathbf e < 2.72$
& $\mathbf e < 2.72$
\\ \hline
\end{tabular}
  \caption{\small Competitive ratios shown for oblivious medians and online bidding.  Ratios in bold are optimal.}
  \label{fig: results}
\vspace*{-0.1in}
\end{figure}

%%%%%%%%%%%%%%%

We also consider here oblivious algorithms that are
\emph{$s$-size-competitive}: they are allowed to use extra medians,
but must achieve the optimal cost for each $k$.  
An algorithm is \emph{$s$-size-competitive} if it produces a
sequence $\barF$ 
such that each set $F_k$ has cost at most $\opt_k$ and
size at most $sk$.
(If the algorithm is randomized, it must produce a random sequence such 
that each set $F_k$ costs at most $\opt_k$ 
and has {\em expected} size at most $sk$.)

To our knowledge, size-competitive algorithms for oblivious medians have
not been studied, although other online problems have been
analyzed in an analogous setting of
\emph{resource augmentation} (e.g.
\cite{KalPru00,ChGoKK04,Koutso99}).
We completely characterize the optimal size-competitive
ratios for oblivious medians:

%%%%%%%%%%%%%%%%%%

\smallskip
\begin{theorem}\label{thm: size competitive}
  {\rm\bf (a)}
  Oblivious medians has
  non-polynomial deterministic and randomized oblivious algorithms
  that are $4$-size-competitive and $e$-size-competitive,
  respectively.
  {\rm\bf (b)} No deterministic or randomized oblivious
  algorithm is less than $4$-size-competitive or $e$-size-competitive,
  respectively.
  {\rm\bf (c)} If offline $k$-median has a polynomial
  $c$-size-competitive algorithm, then the oblivious problem has
  polynomial deterministic and randomized algorithms that are
  $4c$-size-competitive and $ec$-size-competitive, respectively.
\end{theorem}

The upper and lower bounds in Theorem~\ref{thm: size competitive} hold
for both the metric and non-metric problems (with respect to
size-competitiveness, the metric and non-metric problems are
equivalent).  Part (c) on polynomial algorithms is included for
completeness, as is the following result for offline $k$-medians
(proof omitted):

\smallskip

\begin{theorem}\label{thm: offline medians}
  Offline $k$-medians has a polynomial
  $O(\log(n))$-size-approximation algorithm.
\end{theorem}

This improves the best previous result ---
 a bicriteria approximation algorithm that finds a facility set of
size $\ln(n+n/\eps)k$ and cost $(1+\eps)\opt_k$ \cite{young00kmedians}.  
Our algorithm finds a true (not bicriteria) approximate solution:
a facility set of size $O(\log k)$ and cost at most $\opt_k$.

Theorems~\ref{thm: size competitive} and~\ref{thm: offline medians}
imply the size-competitive ratios shown in Fig.~\ref{fig: results}.
Note also that no polynomial algorithm (oblivious or offline) is
$o(\log{}n)$-size-competitive unless P=NP, even for the metric case.

%%%%%%%%%%%%%%%%%%%%%%%

To analyze oblivious medians, we reduce the size- and cost-competitive
oblivious problems to the following folklore 
``\emph{online bidding problem}'':  
An algorithm repeatedly submits ``bids'' $b\in\posreals$, until it
submits a bid $b$ that is at least as large as some unknown threshold
$T\in\posreals$.  Its cost is the total of the submitted bids.  The
algorithm is $\beta$-competitive if, for any $T\in\posreals$, its cost
is at most $\beta T$ (or, if the algorithm is randomized, its expected
cost is at most $\beta T$).  More generally, the algorithm may be
given in advance a closed universe $\calU\subseteq\posreals$, with a
guarantee that the threshold $T$ is in $\calU$ and a requirement
that all bids be in $\calU$. 

For $\calU=\posreals$, it is known that
an optimal deterministic strategy bids increasing
powers of $2$, and that there is a better randomized strategy which 
bids (randomly
translated) powers of $e$. We complete this
characterization
by proving that the randomized strategy is optimal.

%%%%%%%%%%%

\smallskip

\begin{theorem}\label{thm: bidding}
  {\rm\bf (a)}
  Online bidding has deterministic and randomized
  algorithms that are $4$-competitive and $e$-competitive,
  respectively.  Furthermore, if $\calU$ is finite, the algorithms 
  run in time polynomial in $|\calU|$.
  {\rm\bf (b)}
  No deterministic or randomized algorithm is less than
  $4$-competitive or $e$-competitive, respectively, even when restricted to
  instances of the form $\calU=\{1,2,...,n\}$ for some integer $n$.
\end{theorem}

%%%%%%%%%%%%%%%%%%

\myparagraph{Weighted medians.}
All of our results extend to the weighted version,
where we allow the facilities and
the customers to have non-negative weights $w$.
In this case, for a
facility set $X$, one constrains the total weight $\sum_{f\in X} w(f)$
to be at most $k$, and one takes
$\cost(X)=\sum_{u\in\calC}w(u)d_{uX}$.  

%%%%%%%%%%%%%%%%%%

\myparagraph{Approximate triangle inequality.}
Mettu and Plaxton show that their oblivious median algorithm also works
in ``$\lambda$-approximate'' metric spaces, achieving
cost-competitive-ratio $O(\lambda^4)$ \cite{MetPla00,mettu03}.
We reduce this ratio to $O(\lambda^2)$.
We say that the cost function
$d$ is a \emph{$\lambda$-relaxed metric} if $d_{fy} \le \lambda
(d_{fx}+ d_{xg} + d_{gy})$ for any $f,g\in\calF$ and $x,y\in \calC$.
(This is a less restrictive condition than assumed by Mettu and
Plaxton, but it appears that their analysis would go through with this
condition too.  A related concept was studied in
\cite{faginstockmeyer98}.)
Theorem~\ref{thm: cost competitive} generalizes as follows
(proofs omitted):

%%%%%%%%%%%%%%%%%%%%%%%

\smallskip

\begin{theorem}\label{thm: cost competitive2}
  {\rm\bf (a)} Oblivious $\lambda$-relaxed metric medians has
  (non-polynomial) deterministic and randomized algorithms that are
  $8\lambda^2$-cost-competitive and $2e\lambda^2$-cost-competitive,
  respectively.
  {\rm\bf (b)} If offline $\lambda$-relaxed metric $k$-median has a
  polynomial $c$-cost-approximation algorithm, then the oblivious
  problem has deterministic and randomized polynomial algorithms
  that are $8\lambda^2c$-cost-competitive and
  $2e\lambda^2c$-cost-competitive, respectively.
\end{theorem}

%%%%%%%%%%%

\myparagraph{The $kl$-medians problem.}
A natural question to ask is whether better competitive
ratios are possible if the number of medians can take
only some limited number of values. As shown in \cite{MetPla00,mettu03},
no algorithm can be better than $2$-competitive even when
there are
only two possible numbers of medians, either $1$
or $k$, for some large $k$. Here,
we solve the deterministic $k,l$-median problem (where the
number of medians is either $k$ or $l > k$).

\smallskip

\begin{theorem}\label{thm: kl-medians}
For any $k<l$, there is a
deterministic oblivious algorithm for $kl$-medians with
competitive ratio $2-1/l$, and no better ratio is
possible.
\end{theorem}

%%%%%%%%%%%

\myparagraph{Oblivious fractional medians.}
A \emph{fractional $k$-median} is a solution to the linear program
which is the relaxation of the standard integer program
for the $k$-median problem.
The natural \emph{oblivious} version of this
fractional problem is to find a $c\ge 1$ and, for every integer
$k\in[n]$ simultaneously, a pair $(x_{if}^{(k)}),(y_f^{(k)})$ meeting
the constraints of the above linear program, as well as $y_f^{(k)}\leq
y_f^{(k+1)}$ (for all $f$) and
$\sum_u\sum_f{}x_{uf}d_{uf}\le{}c\cdot\opt_k$ (where $\opt_k$ is the
minimum cost of any fractional $k$-median).  The goal 
is to minimize the competitive ratio $c$.

The proof of the theorem below (omitted) extends the proof of
Theorem~\ref{thm: cost competitive},
along with the observation that the randomized algorithm for the
fractional problem can be derandomized without increasing the
competitive ratio. 

%%%%%%%%%%%%

\smallskip

\begin{theorem}\label{thm: fractional oblivious median}
  Oblivious fractional metric medians has a deterministic polynomial
  algorithm that is $2e$-cost-competitive.
\end{theorem}

%%%%%%%%%%%%%%

\myparagraph{Bicriteria approximations.}
Combining Theorem~\ref{thm: size competitive}, Theorem~\ref{thm:
  reduction}, and offline bicriteria results from
\cite{arya01,lin92,lin92packing,korupolu00}, we can obtain oblivious,
polynomial algorithms with the following bicriteria
$(c,s)$-competitiveness guarantees for oblivious metric medians.  The
first quantity $c$ is the cost-competitive ratio and
the second quantity $s$ is the size-competitive ratio:
(a) $(3+\epsilon,4)$, for any $\epsilon > 0$, (b) $(2+\epsilon ,
4(1+2\epsilon^{-1}))$, for any $\epsilon > 0$, (c) $(1+\epsilon ,
4(3+5\epsilon^{-1}))$, for any $\epsilon > 0$.
% superseded by log(n)-size competitive result:
%(d) $(1+\epsilon,4\ln(n+n\epsilon^{-1}))$, for any $\epsilon > 0$,
%                for the non-metric case.

%%%%%%%%%%%%%%

\myparagraph{Notation.}
Throughout we use the following terminology for online bidding.  Given
the universe $\calU$, the algorithm outputs a {\em bid set}
$\calB\subseteq\calU$. Against a particular threshold $T$, the
algorithm pays for the bids $\{b\in\calB : b\le{}T^+\}$, where
$T^+=\min\{b\in\calB : b\ge{}T\}$.  The bid set $\calB$ is {\em
  $\beta$-competitive} if, for any $T\in\calU$, this payment is at
most $\beta T$.
Also, $\posreals$ denotes the set of non-negative
reals, $\integers$ the set of integers, and $\posnaturals$ the set of
positive integers.  For $n\in\posnaturals$, let
$[n]=\braced{1,2,\dots,n}$.

%%%%%%%%%%%%%%%%%%%

\myparagraph{Plan of the paper.}
We prove our upper bounds on competitive algorithms for oblivious
medians (Theorem~\ref{thm: cost competitive} for cost-competitive
algorithms and Theorem~\ref{thm: size competitive}(a) for
size-competitive algorithms) by reducing oblivious medians to online
bidding (Theorem~\ref{thm: reduction}, below) and then proving the
upper bounds for online bidding (Theorem~\ref{thm: bidding}).
%
We prove our lower bounds on size-competitive algorithms for oblivious
medians (Theorem~\ref{thm: size competitive}(b)) by reducing
online bidding to size-competitive medians (Theorem~\ref{thm: size
  lb}, below) and then proving the lower bounds for online bidding in
Theorem~\ref{thm: bidding}.
%
We prove the reductions in Section~\ref{section: reductions}
and analyze online bidding in Section~\ref{sec: bidding}.
In Section~\ref{sec: kl-medians} we prove 
Theorem~\ref{thm: kl-medians}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Oblivious medians and online bidding}
\label{section: reductions}

We start by showing that
oblivious medians can be reduced to online bidding.
We show that (a) $2c\beta$-cost-competitive oblivious metric medians
reduces (in polynomial time) to $\beta$-competitive online bidding and
$c$-cost-approximate offline medians, and (b)
$s\beta$-size-competitive oblivious medians reduces (in polynomial time)
to $\beta$-competitive online bidding and $s$-size-approximate offline
medians.

Note that part (b) holds even for non-metric medians.  Also, if allowing
non-polynomial time, one can take $F^*_k$ to be the optimal $k$-median
in Theorem~\ref{thm: reduction}, which
is both $1$-cost-approximate and $1$-size-approximate; then
the oblivious solution $\barF$ is {\rm (a)} $2\beta$-cost-competitive or
{\rm (b)} $\beta$-size-competitive.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}\label{thm: reduction}
  Let $\beta\geq 1$ and assume that there exists a
  polynomial $\beta$-competitive algorithm for online bidding.
  Fix an instance of $k$-median.
  
  {\rm\bf (a)}
  In the metric case, suppose that for each $i\in [n]$ we have a set
  of facilities
  $F_i^*$ with $|F_i^*|\le i$ and $\cost(F_i^*)\le c\cdot\opt_i$.
  Then in polynomial time we can
  compute an  \emph{oblivious} solution $(F_i)_i$ where
   $|F_i|\le i$ and $\cost(F_i)\le 2c\beta\cdot\opt_i$.
  
  {\rm\bf (b)}
  Suppose that for each $i\in [n]$, we have a set 
  of facilities $F_i^*$ witht $|F_i^*|\le s\cdot i$
  and $\cost(F_i^*)\le \opt_i$. Then in polynomial time
 we can compute an \emph{oblivious} solution $(F_i)_i$ where
 $|F_i| \le s\beta\cdot i$ and $\cost(F_i)\le \opt_i$.

  If the algorithm for online bidding is randomized,
  then the computations in (a) and (b) are also randomized.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{proof} 
  We first prove part (a) of Theorem~\ref{thm: reduction}
 in the deterministic case.  The
  proof in the randomized setting is similar and we omit it.
  
  For convenience, we introduce distances between facilities: given
  two $f,g\in\calF$, let $d'_{fg} = \min_{x\in\calC}(d_{fx}+d_{xg})$.
  This extension satisfies the triangle inequality.
  By assumption, each $F^*_k$ is $c$-cost-approximate:
  $|F^*_k| \le k$ and $\cost(F^*_k)\le c\cdot\opt_k$.  Assume without
  loss of generality that $\cost(F^*_k) \le \cost(F^*_{k+1})$ for all $k$.
  
  The algorithm constructs the oblivious solution $(F_i)_i$ from $(F_i^*)_i$ 
  in several steps.  First, fix some index set $\calK\subseteq[n]$,
  with $1\in\calK$, by a method to be described later, and let
  $\kappa(1),\kappa(2),\ldots,\kappa(m)$ denote the indices in
  $\calK$ in increasing order.
  Next, compute $F_k$ just for $k\in\calK$.
  Start by defining $F_{\kappa(m)} = F^*_{\kappa(m)}$.
  Then, working backwards, inductively
  define $F_{\kappa(i)}$ to contain
  the facilities within $F_{\kappa(i+1)}$
  that are ``closest'' to $F^*_{\kappa(i)}$. 

 More precisely, given two subsets $A,B$ of ${\cal F}$, 
let $\Gamma(A,B)$
denote a subset $\Gamma$ of $B$, minimal with respect to inclusion, and such
that $d'_{\mu{}\Gamma}=d'_{\mu{}B}$ for all $\mu\in{}A$ (breaking
  ties arbitrarily). Obviously, $|\Gamma(A,B)|\le|A|$,
  and $\Gamma(A,B)$ can be computed in polynomial time given
  $A$ and $B$. Then
  \(\displaystyle{}F_{\kappa(i)}=\Gamma(F^*_{\kappa(i)},F_{\kappa(i+1)})\). 

  
  Finally, define $F_k$ for $k\in[n]\setminus\calK$ as follows.
  Let $k^-=\max\{i\in\calK:i\le{}k\}$
  (it is well defined, since $1\in\calK$.)
  Define $F_k = F_{k^-}$.
  To complete the construction, it remains to describe how
  to compute $\calK$, which we momentarily defer.

  To analyze the size, note that $|F_k|\le k$, 
  because for $k\in\calK$, by  definition
  of $\Gamma$ we have $|F_k|\le|F^*_k|\le k$, while for $k\not\in\calK$, we
  have $|F_k|=|F_{k^-}|\le{}k^-<k$.  
  
  To analyze the cost, we use the following lemma.
  (The proof can be found in \cite{cky05} and is also
         implicit in \cite{jain01}.)

%%%%%%%%%%%

\begin{lemma}\label{fact: cost of Fk}
Assume that the distance function is metric, and
consider  any two sets $A,B\subseteq\calF$ and let $\Gamma=\Gamma(A,B)$. 
Then for every $x\in X$ we have
$c_{x\Gamma}\leq 2c_{xA}+c_{xB}$.
\end{lemma}

\noindent   We now claim that
%
  \begin{equation}
  \cost(F_k)~\le~2\sum_{\ell \ge k^-, \ell\in\calK} \cost(F^*_\ell).
                \label{eqn: cost of Fk}
  \end{equation}
%
  Indeed, for indices $k\in\calK$, we have $k = k^-$, and
  (\ref{eqn: cost of Fk}) follows from Lemma~\ref{fact: cost of Fk} summed
over all $x$ and from
  the construction of $F_k$ (for $k=\kappa(m),\ldots,\kappa(1)$).
  For $k\not\in\calK$, inequality (\ref{eqn: cost of Fk}) holds as well,
  simply because $F_{k} = F_{k^-}$, the bound holds for $k=k^-$, and
  $(k^-)^- = k^-$.
  
  Since $\cost(F^\ast_k) \le c\,\opt_k$, to make $F$
  $2c\beta$-cost-competitive we will choose $\calK$ so that,
  for all $k$,
%
  \begin{equation}\label{eqn: cost}
    \sum_{\ell\ge{}k^-,\ell\in\calK}\cost(F^*_\ell)~\le~\beta\,\cost(F^*_k).
  \end{equation}
  
  To compute the set $\calK$, let
  $\calU=\{\cost(F^*_n),\cost(F^*_{n-1}),\ldots,\cost(F^*_1)\}$ and
  take $\calB$ to be any $\beta$-competitive bid set for universe $\calU$.
  Define $\calK=\{\kappa(m),\kappa(m-1),\ldots,\kappa(1)\}$ to be a minimal
  set (containing 1) such that the bid set is \( \calB =
  \{\cost(F^*_{\kappa(m)}),\cost(F^*_{\kappa(m-1)}),
  \ldots,\cost(F^*_{\kappa(1)})\}.  \) Then the left-hand side
  of~(\ref{eqn: cost}) is exactly the sum of the bids paid from the
  bid set for threshold $T=\cost(F^*_k)$.  Since the bid set is
  $\beta$-competitive, this is at most $\beta\,\cost(F^*_k)$,
  so~(\ref{eqn: cost}) holds.
  This completes the proof of part (a).

%  \myparagraph{Remark.} This reduction is just one possible proof for
%  Theorem~\ref{thm: cost competitive}(a). It can also be proved
%  directly by defining ${\calK}$ inductively, setting $\kappa (1)=1$
%  and defining $\kappa(i+1)$ to be minimum such that
%  $\cost(F^*_{\kappa(i+1)})\leq \cost(F^*_{\kappa(i)})/2.$

  We now prove part (b) of Theorem~\ref{thm: reduction}.
  By assumption each $F^*_k$ is $s$-size-approximate,
  that is, $|F^*_k| \le s k$ and $\cost(F^*_k)\le \opt_k$.
  
  Fix some $\beta$-competitive bid set $\calB$.
  Let $\calB_k$ be the set of bids in $\calB$ paid 
  against threshold $T=k$ with $\calU=[n]$.
  Define $F_k = \bigcup_{b\in \calB_k} F_b^*$. 
  Then $\barF = (F_1,F_2,...,F_n)$ is an oblivious solution
  because $\calB_k \subseteq \calB_{\ell}$ for $\ell\ge k$.
  Further, $\cost(F_k) \le \opt_k$
  because $F_k$ contains $F^*_b$ for some $b\ge k$, so $\cost(F_k)
  \le \cost(F^*_b) \le \opt_b \le \opt_k$.  
  Since $\calB$ is $\beta$-competitive, we have $|F_k| \le
  \sum_{b\in \calB_k} |F_b^*| \le \sum_{b \in \calB_k} s b \le s \beta k$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Our next reduction shows that competitive online bidding reduces to
size-competitive oblivious medians.
Note that, together with Theorem~\ref{thm: reduction}(b), this implies
that online bidding and size-competitive oblivious medians are
equivalent.

%%%%%%%%%%%%%%%%%%%%%%

\smallskip

\begin{theorem}\label{thm: size lb}
  Let $s\geq 1$ and assume that, for oblivious medians ( metric or not), there is a
  (possibly randomized)
  $s$-size-competitive algorithm.  Then, for any
  integer $n$, 
  there is a (randomized) $s$-competitive algorithm
for online bidding with $\calU=[n]$.
\end{theorem}

\begin{proof}
  We give the proof in the deterministic setting. (The proof in the
  randomized setting is similar and we omit it.)
  For any arbitrarily large $m$,  we construct sets $\calC$
of customers and $\calF$ of facilities, a metric distance
function $d_{uf}$, for $u\in\calC$ and $f\in\calF$. 
The facility set $\calF$ will be partitioned 
into sets $M_1,M_2,\dots, M_m$,
where $|M_k| = k$ for each $k$, with the following properties:
{(i)}
    For all $k$, $\cost(M_k) > \cost(M_{k+1})$, and
{(ii)}
    For all $k$, and for every set $F$ of facilities,
    if $\cost(F)\le \cost(M_k)$ then there exists
    $\ell\ge k$ such that $M_\ell$ is contained in $F$.
  These conditions imply that each $M_k$ is the unique
  optimum $k$-median.
  
  Assume for the moment that there exists such a metric space,
and consider an $s$-size-competitive oblivious median $\barF$ for it.
Let $\calB=\{k:M_k\subseteq{}F_k\}$.
We show that $\calB$ is an
  $s$-competitive bid set for universe $\calU=[m]$.  Against any
  threshold $T\in[m]$, the total of the bids paid will be
%
\begin{equation}\label{exp: 1}
X=\sum\{ k : k < T, M_k\subseteq F_k\}
  ~+~ \min\{\ell : \ell \ge T, M_\ell \subseteq F_\ell\}
\end{equation}
%
Now, $\sum\{ k : k < T, M_k\subseteq F_k\}\le \sum\{ k : k < T, M_k\subseteq F_T\}$ since $\barF$ is a nested sequence.  Similarly, 
we have
$$
\min\{\ell : \ell \ge T, M_\ell \subseteq F_\ell\}
\le \min\{\ell : \ell \ge T, M_\ell \subseteq F_T\}
$$  
(By (ii), $M_\ell \subseteq F_T$ for some $\ell\ge T$,
  so the minimum on the right is well-defined for $T\in[m]$.)
Thus:
\begin{eqnarray*}
X&\leq & 
\sum\{ k : k < T, M_k\subseteq F_T\}+\min\{\ell : \ell \ge T, M_\ell \subseteq F_T\}\\
&= &
\sum\{ |M_k| : k < T, M_k\subseteq F_T\}+\min\{|M_\ell| : \ell \ge T, M_\ell \subseteq F_T\}~~~\hbox{since }|M_k|=k\\
&\leq & 
\sum\{ |M_k| :  M_k\subseteq F_T\}\\
&\leq& 
|F_T|~~~\hbox{since the $M_k$'s are disjoint}\\
&\leq &
sT~~~\hbox{ since $\barF$ is $s$-size-competitive.}
\end{eqnarray*}
Thus, the bid set $\calB$ is $s$-competitive for universe $\calU=[m]$.

  \medskip

  We now present the construction of the metric space satisfying
  conditions (i) and (ii). Let $\calC$
be the set of integer vectors
  $\baru = (u_1,u_2,\dots,u_m)$ where $ u_\ell \in [1, \ell ]$ for all $\ell=1,2,\dots,m$.
  For each $\ell\in [1,m]$, introduce a set
  $M_\ell = \braced{\mu_{\ell,1},\mu_{\ell,2},\dots,\mu_{\ell,\ell}}$,
  and for each  node $\baru$ in $\calC$,
connect $\baru$ to $\mu_{\ell,u_\ell}$  with an edge of
  length $\delta_\ell = 1 + (m!)^{-\ell}$.
  The set of facilities is $\calF = \bigcup_\ell M_\ell$.
  All distances between points in $\calC\cup\calF$
  other than those specified above are determined
  by shortest-path distances. The resulting distance function 
  satisfies the triangle inequality.

  We have $\cost(M_j) =  m!\delta_j$ for each $j\in [1,m]$, so (i) holds.
  We prove (ii) by contradiction. Fix some index $j$ and
  consider a set $F\subseteq\calF$ that does not contain
  $M_\ell$ for any $\ell\ge j$: for each $\ell\ge j$ there is $i_\ell\le \ell$
  such that $\mu_{\ell,i_\ell}\notin F$. Define a customer
  $\baru$ as follows: $u_i = 1$ for $\ell = 1,\dots,j-1$ and
  $u_i = i_\ell$ for $\ell = j,\dots,m$. Then the facility $\mu_{\ell,i}\in F$
  serving this $\baru$ must have  $\ell < j$ or $i\neq i_\ell$.
  Either way, it is at distance at least
  $\delta_{j-1}$ from $\baru$. Since each other customers pays
         strictly more than 1, we get
  $\cost(F) > m!-1 + \delta_{j-1}
  = m!\delta_j = \cost(M_j)$ -- a contradiction.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Online bidding}
\label{sec: bidding}

In this section we prove Theorem~\ref{thm: bidding}. For completeness,
we give proofs of the (folklore) deterministic and randomized 
upper bounds and deterministic lower
bound.   The upper bound uses a doubling algorithm that has been used in several papers,
first in~\cite{krt96,motwani94nonclairvoyant} and later 
in~\cite{gk96,chakrabarti96improved,cfm97,dl05}.
Our main new contribution in this section is a new randomized lower bound that matches the upper bound. 
(The proof of Lemma~\ref{lem: finite lower bound 1}
was communicated to us by Yossi Azar.)

%%%%%%%%%%%%%%%%%

\smallskip
\begin{lemma} \label{lem: bidding det ub}
  For online bidding, there is a deterministic $4$-competitive
  algorithm.  If $\,\calU$ is finite, the algorithm runs in time
  polynomial in $|\calU|$.
\end{lemma}

\begin{proof}
  First consider the case $\calU=\posreals$.  Define the
  algorithm to produce the set of bids $\{0\}\cup\{2^j:j\in\naturals\}$.
Let $i = \ceiling{\log_2 T}$, where $T>0$
is the threshold: the
  algorithm pays $\sum_{j \le i} 2^j = 2^{i+1} \le 4T$, hence
 is 4-competitive.
  
  Next, we reduce the general case  to the case
  $\calU=\posreals$.  Knowing that $T\in\calU$, the algorithm, when it would
have bid
  $b\not\in\calU$,  will  instead bid the next smaller bid in
  $\calU$ (if there is one, and otherwise the bid is skipped).  
  This  only decreases the cost the
  algorithm pays against any threshold $T\in\calU$.
  Note that the modified algorithm can be implemented in time
  polynomial in $|\calU|$ if $\calU$ is finite.
\end{proof}

%%%%%%%%%%%%%%%%

\smallskip

\begin{lemma}\label{lem: finite lower bound 1}
  For online bidding, no deterministic algorithm is less than
  $4$-competitive, even for $\calU=\posnaturals$.
\end{lemma}

\begin{proof}
let $x_n$ be the $n$th bid,  $s_n = \sum_1^n x_i$ and 
$y_n = s_ {n+1}/s_n$.
Suppose, for a contradiction, that there exists $a<4$ such that
$s_{n+1}/x_n < a $  for all $n$. Rewriting, we get
$ y_{n+1} \leq (1-1/y_n) a$.
Since $ 1-1/z < z/4$, this implies 
    $y_{n+1} < (y_n/4) a$;
thus $y_n < (a/4)^n  y_0$, and so eventually $s_{n+1} < s_n$, which is a  contradiction. 
\end{proof}

%%%%%%%%%%%%%%%%%

\smallskip

\begin{lemma}\label{lem: bidding rand upper bound}
  For online bidding, there is a randomized $e$-competitive algorithm.
  If $\,\calU$ is finite, then the algorithm runs in time polynomial in
  $|\calU|$.
\end{lemma}

\begin{proof}
  First we consider the case $\calU=\posreals$.  
 Pick a real number $\xi\in(0,1]$
  uniformly at random, then choose the set of bids
  $\calB=\{0\}\cup\{e^{i+\xi}:i\in\naturals\}$.
    
  For the analysis, let random variable $b$ be the largest bid paid by the algorithm
  against threshold $T>0$.
  The total paid by the algorithm is less than
  $\sum_{i=0}^\infty b e^{-i} = be/(e-1)$.
  Since $b/T$ is distributed like $e^{\xi}$
  where $\xi$ is distributed uniformly in $[0,1)$,
  the expectation of $b$ is $T\int_0^1 e^z \,dz = T(e-1)$.
  Thus, the expected total payment is $eT$,
  and the algorithm is $e$-competitive.
  
  The general case  reduces to
  the case $\calU=\posreals$ just as in the proof of Lemma~\ref{lem:
    bidding det ub}.  
\end{proof}

%%%%%%%%%%

\smallskip

\begin{lemma}\label{duality}
  Fix any $n\in\posnaturals$.
  Suppose $\mu:[n] \rightarrow \posreals$ and
  $\pi:[n] \rightarrow \posreals$ satisfy
  \begin{equation}\label{eqn: dual}
  \sum_{T=t}^n \frac{1}{T}\pi(T) ~\ge~ 
  \frac{1}{b} \sum_{T=t}^{b} \mu(T)
  ~~~(\forall b,t: 1\le t \le b \le n).
  \end{equation}
  For online bidding with $\calU=[n]$, there is no
  randomized algorithm with
  competitive ratio better than
  $\sum_{T=1}^n \mu(T)~/~\sum_{T=1}^n \pi(T)$.
\end{lemma}

\begin{proof}
  Consider a random set $\calB$ of bids generated by any $\beta$-competitive
  randomized algorithm when $\calU=[n]$.  Without loss of generality, the
  maximum bid in $\calB$ is $n$.
  
  Let $\calB=\{b_1,b_2,\ldots,b_m=n\}$ be the ordered sequence of bids in $\calB$.
  Consider the sequence of intervals
  $([1,b_1],[b_1+1,b_2],[b_2+1,b_3],\ldots,[b_{m-1}+1,b_m])$, 
  which exactly covers the points $1,2,\ldots,n$.  
  Let $x(t,b)$ denote the probability (over all random $\calB$) 
  that $[t,b]$ is one of these intervals.  
  The algorithm pays bid $b$ against threshold $T$ 
  if and only if, for some integer $t\le T$, $[t,b]$ is one of these intervals.  
  Thus, for any threshold $T$ and bid $b$,
  $\sum_{t=1}^T x(t,b)$ is the probability that bid $b$ is made
  against threshold $T$.  (We will use this below.)
  
  We claim that $\beta$ and $x$ form a feasible solution to the following
  linear program (LP):
 % 
  \[\mbox{minimize}_{\beta,x}~ \beta \mbox{~~subject to~}
  \left\{\begin{array}{rcll}
      \displaystyle
      \beta - \sum_{b=1}^n \frac{b}{T} \sum_{t=1}^T x(t,b) & \ge & 0
    &(\forall T\in[n])
    \\
    \displaystyle
    \sum_{b=T}^n\sum_{t=1}^T x(t,b) & \ge & 1 
    &(\forall T\in[n])
    \\
    x(t,b) & \ge & 0  &(\forall t,b\in[n]).
  \end{array}\right.
\]
%
 The first constraint is met because, 
    for any threshold $T$, $\sum_{t\le T;b} b\, x(t,b)$ 
    is the expected sum of the bids made
    by the algorithm if $T$ is the threshold.
    This is at most $\beta T$ because 
    the algorithm has competitive ratio $\beta$.
 The second constraint is met because for any threshold $T$, 
    the algorithm must have at least one bid above the threshold, hence
    at least one $[t,b]$ with $t\leq T\leq b$.

  Thus, the value of this linear program (LP) is a lower bound on the
  optimal competitive ratio of the randomized algorithm.
  To get a lower bound on the value of (LP), we use the dual (DLP)
(where the dual variables $\mu (T)$ correspond to the first set of
constraints and $\pi (T)$ to the second set of constraints):
  \[
    \mbox{maximize}_{\mu,\pi}~ \sum_{T=1}^n \mu(T)~
    \mbox{~~subject to~}
    \left\{\begin{array}{rcll}
    \displaystyle
    \sum_{T=1}^n \pi(T) & \le & 1 
    \\
    \displaystyle
    \sum_{T=t}^b \mu(T)~
    - \sum_{T=t}^n \frac{b}{T}\,\pi(T)~ &\le& 0
    &(\forall t,b\in[n])
    \\
    \mu(T),\pi(T)&\ge& 0 &
    (\forall T\in[n]).
  \end{array}
  \right.
  \]

  Now, given any $\mu$ and $\pi$ meeting the condition of the lemma,
  if we scale $\mu$ and $\pi$ by dividing by $\sum_T \pi(T)$, we
  get a feasible dual solution whose value is 
  $\sum_T \mu(T)~/ \sum_T \pi(T)$.
  Since the value of any feasible dual solution
  is a lower bound on the value of any feasible solution to the primal,
  it follows that the competitive ratio $\beta$
  of the randomized algorithm is at least  $\sum_T \mu(T)~/ \sum_T \pi(T)$.
\end{proof}

%%%%%%%%%%%%%%%%%%%

\begin{lemma}\label{lem: bidding rand lb}
  There exists $\mu:[n]\rightarrow\posreals$ and
  $\pi:[n]\rightarrow\posreals$ satisfying
  Condition~(\ref{eqn: dual}) of Lemma~\ref{duality}
  and such that 
  $\sum_T \mu(T) / \sum_T \pi(T) \ge (1-o(1))e$.
\end{lemma}

\begin{proof}
  Fix $U$ arbitrarily large 
and let $n=\lceil U^2\log U \rceil$.
  Let $\alpha>0$ be a constant to be determined later:
  We will choose $\alpha$ so that Condition~(\ref{eqn: dual}) 
  holds, and then show that the corresponding lower bound is
  $e(1-o(1))$ as $U\rightarrow\infty$.
  Define
  \[\mu(T) = \begin{cases}
    \alpha/T & \textrm{if\ } U \le T \le U^2 \cr
    0 & \textrm{otherwise}
  \end{cases}
  \mbox{~~~~and~~~}
  \pi(T) = \begin{cases}
    1/T & \textrm{if\ } U \le T \le U^2\log U \cr
    0 & \textrm{otherwise.}
  \end{cases}.\]

  If $T\ge U^2$,
  then the right-hand side of Condition~(\ref{eqn: dual}) has value 0, so the condition holds
  trivially.  On the other hand,  since $\pi(T)$ and $\mu(T)$
  are zero for $T<U$, if the condition holds for $T=U$, then it also holds
  for $T<U$.  So, we need only verify the condition for $T$ in the
  range $U\le T \le U^2$.
  The expression on the left-hand side of~(\ref{eqn: dual}) then has value
  \[ 
  \sum_{T=t}^{U^2\log U} \frac{1}{T^2}
  ~\ge~
  \int_{t}^{1+U^2\log U} \frac{1}{T^2}~dT
  ~=~
  \frac{1}{t} - \frac{1}{1+U^2\log U}
  ~\ge~
  \frac{1}{t} - \frac{1}{t\log U}
  ~=~
  \frac{1}{t}(1 - o(1)).
  \]
  In comparison, the expression on the right-hand side has value at
  most
  \[
  \max_{b\ge t}~ \frac{1}{b} \sum_{T=t}^b \frac{\alpha}{T}~
  ~\le~
  \alpha
  \max_{b\ge t}~ \frac{1}{b} \int_{t-1}^b \frac{1}{T}~dT
  ~=~
  \alpha \max_{b\ge t}~ \frac{1}{b} \ln\frac{b}{t-1}
  ~=~
  \frac{\alpha}{e\,t(1-o(1))}
  \]
  (The second equation follows by calculus, for
         the maximum occurs when $b=e(t-1)$.)
  Thus, Condition ~(\ref{eqn: dual})
  is met for $\alpha = (1-o(1))e$.
  Then,
  Lemma~\ref{duality} gives a lower bound on the competitive ratio of 
  \[
  \frac{\sum_{T} \mu(T)}{\sum_{T} \pi(T)}
  ~=~
  \frac{\sum_{T=U}^{U^2} \alpha/T}{%
    \sum_{T=U}^{U^2\log U} 1/T}
  ~=~
  (1-o(1))\alpha\frac{\ln (U^2/U) }{\ln( (U^2\log U)/ U)}
  ~=~
  (1-o(1))e.
  \]
\end{proof}

Theorem~\ref{thm: bidding} follows directly from Lemmas
\ref{lem: bidding det ub},
\ref{lem: finite lower bound 1},
\ref{lem: bidding rand upper bound}, 
\ref{duality}, and
\ref{lem: bidding rand lb}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Oblivious Algorithms for $kl$-Medians}
\label{sec: kl-medians}

In this section we sketch the proof
of Theorem~\ref{thm: kl-medians}.
Formally, in the $kl$-median problem we need to compute
two sets $F_k \subseteq F_l$ with $|F_k| = k$ and $|F_l| = l$,
minimizing the competitive ratio
$R = \max\braced{ \cost(F_k)/opt_k , \cost(F_l)/opt_l }$.

\paragraph{The lower bound.}
The lower bound is a slight refinement of the one
in \cite{MetPla00,mettu03}.
Consider the following metric space. It consists of $l$
customers, where customers $j$ is
connected to facility $g_j$ by an edge of length $\delta = 1/l$.
All customers are also connected to a facility $f$
with edges of length $1$:

Let $G = \braced{g_1,\dots,g_l}$. Then $G$ is the optimal
$l$-median. We have
$\cost(f) =l$,
$\cost(G) = l\delta$,
$\cost(g_i) = \delta + (l-1)(2+\delta)$,
and $\cost(G-g_i+f) = (l-1)\delta + 1$.
So for $\delta = 1/l$, we get:
%
\begin{eqnarray*}
\frac{\cost(g_i)}{\cost(f)} \;=\; 2-1/l
\quad\quad\textrm{and}\quad\quad
\frac{\cost(G-g_i+f)}{\cost(G)} \;=\; 2-1/l
\end{eqnarray*}
%

%%%%%%%%%%%%%%%%%%%%%

\paragraph{The upper bound.}
Let $F$ and $G$ denote, respectively, the optimum $k$-median and 
the optimum $l$-median. The algorithm choosese
the better of two options: either
{(a)}
$F_k = F$ and $F_l = F\cup G-X$,
where $X\subseteq G$ is a set of cardinality $k$ that
minimizes $\cost(F\cup G-X)$,
or
{(b)}
$F_k = Y$, where $Y\subseteq G$ is a set of cardinality $k$
that minimizes $\cost(Y)$, and $F_l = G$.

The competitive analysis of this algorithm
is based on a probabilistic argument and will
appear in the full version of this paper.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Acknowledgments.}
We are grateful to anonymous referees for suggestions
to improve the presentation. We also wish to thank Yossi Azar
for pointing out references to previous results on online bidding
and providing a simpler proof of
Lemma~\ref{lem: finite lower bound 1}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\small
\bibliographystyle{plain}
\bibliography{other}
}

\end{document}



final_latin.bbl
\begin{thebibliography}{10}

\bibitem{ArRaSh03}
A.~Archer, R.~Rajagopalan, and D.B. Shmoys.
\newblock Lagrangian relaxation for the k-median problem: new insights and
  continuity properties.
\newblock In {\em Proc{.} 11th European Symp{.} on Algorithms (ESA)}, pages
  31--42, 2003.

\bibitem{arya01}
V.~Arya, N.~Garg, R.~Khandekar, K.~Munagala, and V.~Pandit.
\newblock Local search heuristic for k-median and facility location problems.
\newblock In {\em Proc{.} 33rd Symp{.} Theory of Computing (STOC)}, pages
  21--29. ACM, 2001.

\bibitem{chakrabarti96improved}
S.~Chakrabarti, C.A. Phillips, A.S. Schulz, D.B. Shmoys, C.~Stein, and J.~Wein.
\newblock Improved scheduling algorithms for minsum criteria.
\newblock In {\em Automata, Languages and Programming}, pages 646--657, 1996.

\bibitem{cfm97}
M.~Charikar, C.~Chekuri, T.~Feder, and R.~Motwani.
\newblock Incremental clustering and dynamic information retrieval.
\newblock In {\em Proc{.} 29th Symp{.} Theory of Computing (STOC)}, pages
  626--635. ACM, 1997.

\bibitem{charikar99b}
M.~Charikar and S.~Guha.
\newblock Improved combinatorial algorithms for the facility location and
  k-median problems.
\newblock In {\em Proc{.} 40th Symp{.} Foundations of Computer Science (FOCS)},
  pages 378--388. IEEE, 1999.

\bibitem{charikar99a}
M.~Charikar, S.~Guha, E.~Tardos, and D.B. Shmoys.
\newblock A constant-factor approximation algorithm for the k-median problem.
\newblock In {\em Proc{.} 31st Symp{.} Theory of Computing (STOC)}, pages
  1--10. ACM, 1999.

\bibitem{ChGoKK04}
C.~Chekuri, A.~Goel, S.~Khanna, and A.~Kumar.
\newblock Multi-processor scheduling to minimize flow time with $\eps$-resource
  augmentation.
\newblock In {\em Proc{.} 36th Symp{.} Theory of Computing (STOC)}, pages
  363--372. ACM, 2004.

\bibitem{cky05}
M.~Chrobak, C.~Kenyon, and N.E. Young.
\newblock The reverse greedy algorithm for the $k$-median problem.
\newblock {\em Information Processing Letters}, 97:68--72, 2006.

\bibitem{dl05}
S.~Dasgupta and P.M. Long.
\newblock Performance guarantees for hierarchical clustering.
\newblock {\em Journal of Computer and System Sciences}, 70(4):555--569, 2005.

\bibitem{faginstockmeyer98}
R.~Fagin and L.~Stockmeyer.
\newblock Relaxing the triangle inequality in pattern matching.
\newblock {\em IJCV: International Journal of Computer Vision}, 30:219--231,
  1998.

\bibitem{gk96}
M.~Goemans and J.~Kleinberg.
\newblock An improved approximation ratio for the minimum latency problem.
\newblock In {\em Proc{.} 7th Symp{.} on Discrete Algorithms (SODA)}, pages 152
  -- 158. ACM/SIAM, 1996.

\bibitem{jain02}
K.~Jain, M.~Mahdian, and A.~Saberi.
\newblock A new greedy approach for facility location problems.
\newblock In {\em Proc{.} 34th Symp{.} Theory of Computing (STOC)}, pages
  731--740. ACM, 2002.

\bibitem{jain01}
K.~Jain and V.V. Vazirani.
\newblock Approximation algorithms for metric facility location and k-median
  problems using the primal-dual schema and lagrangian relaxation.
\newblock {\em Journal of ACM}, 48:274--296, 2001.

\bibitem{KalPru00}
B.~Kalyanasundaram and K.~Pruhs.
\newblock Speed is as powerful as clairvoyance.
\newblock {\em J{.} ACM}, 47:214--221, 2000.

\bibitem{krt96}
M.~Kao, J.H. Reif, and S.~Tate.
\newblock Searching in an unknown environment: An optimal randomized algorithm
  for the cow-path problem.
\newblock {\em Information and Computation}, 131(1):63--80, 1996.
\newblock Preliminary version appeared in the Proceedings of the Symp.\ on
  Discrete Algorithms, Austin, TX, Jan 1993.

\bibitem{korupolu00}
M.R. Korupolu, C.G. Plaxton, and R.~Rajaraman.
\newblock Analysis of a local search heuristic for facility location problems.
\newblock {\em Journal of Algorithms}, 37:146--188, 2000.

\bibitem{Koutso99}
E.~Koutsoupias.
\newblock Weak adversaries for the $k$-server problem.
\newblock In {\em Proc{.} 40th Symp{.} Foundations of Computer Science (FOCS)},
  pages 444--449. IEEE, 1999.

\bibitem{LNRW06}
G.~Lin, C.~Nagarajan, R.~Rajamaran, and D.P. Williamson.
\newblock A general approach for incremental approximation and hierarchical
  clustering.
\newblock In {\em Proc{.} 17th Symp{.} on Discrete Algorithms (SODA)}.
  ACM/SIAM, 2006.

\bibitem{lin92}
J-H. Lin and J.S. Vitter.
\newblock Approximation algorithms for geometric median problems.
\newblock {\em Information Processing Letters}, 44:245--249, 1992.

\bibitem{lin92packing}
J-H. Lin and J.S. Vitter.
\newblock {$\epsilon$}-approximations with minimum packing constraint violation
  (extended abstract).
\newblock In {\em Proc{.} 24th Symp{.} Theory of Computing (STOC)}, pages
  771--782. ACM, 1992.

\bibitem{mettu03}
R.~Mettu and C.G. Plaxton.
\newblock The online median problem.
\newblock {\em SIAM Journal on Computing}, 32:816--832, 2003.

\bibitem{MetPla00}
R.R. Mettu and C.G. Plaxton.
\newblock The online median problem.
\newblock In {\em Proc{.} 41st Symp{.} Foundations of Computer Science (FOCS)},
  pages 339--348. IEEE, 2000.

\bibitem{motwani94nonclairvoyant}
R.~Motwani, S.~Phillips, and E.~Torng.
\newblock Nonclairvoyant scheduling.
\newblock {\em Theoretical Computer Science}, 130(1):17--47, 1994.

\bibitem{young00kmedians}
N.E. Young.
\newblock {\it K}-medians, facility location, and the {C}hernoff-{W}ald bound.
\newblock In {\em Proc{.} 11th Symp{.} on Discrete Algorithms (SODA)}, pages
  86--95. ACM/SIAM, January 2000.

\end{thebibliography}
