92 lines
5.4 KiB
TeX
92 lines
5.4 KiB
TeX
\documentclass[12pt]{article}
|
|
% \usepackage{chao}
|
|
\usepackage[sans]{xenotes}
|
|
% \usepackage{natbib}
|
|
|
|
\title{Exercises in Sariel Har-Peled's \\ \textit{Geometric Approximation Algorithms}}
|
|
\author{}
|
|
\date{}
|
|
|
|
\DeclareMathOperator*{\opt}{OPT}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
% \tableofcontents
|
|
% \newpage
|
|
|
|
For errata and more stuff, see \url{https://sarielhp.org/book/}
|
|
|
|
Note that unless specifically stated, we always consider the RAM model.
|
|
|
|
\section{Grid}
|
|
\begin{exercise}\label{ex1.1}
|
|
Let $P$ be a max cardinality point set contained in the $d$-dimensional unit hypercube such that the smallest distance of point pairs in $P$ is 1. Prove that
|
|
\[\left( \floor{\sqrt{d}}+1 \right)^d \leq |P|\leq \left( \ceil{\sqrt{d}}+1 \right)^d. \]
|
|
\end{exercise}
|
|
hmm... the first exercise in this book is wrong. See \url{https://sarielhp.org/book/errata.pdf}.
|
|
The stated lowerbound is actually an upperbound.
|
|
\begin{proof}
|
|
We evenly partition the $[0,1]$ interval into $m=\left( \floor{\sqrt{d}}+1 \right)$ small segments for each of the $d$ axes. The unit hypercube is partitioned into $m^d$ cells. The length of each cell's diagonal is $\sqrt{\frac{d}{m^2} }< 1$. Thus there is at most one point of $P$ in each cell and there are $\left( \floor{\sqrt{d}}+1 \right)^d$ cells.
|
|
|
|
For lowerbound, one can construct a solution of size $2^d$ by selecting vertices of the hypercube. For sufficient large $d$ one can find a solution of size $(\sqrt{d}/5)^d$.\footnote{Exercise 1.1 (C) in \url{https://sarielhp.org/book/chapters/min_disk.pdf}}
|
|
Let point set $P$ be the optimal solution and let $n=|P|$. We place a $d$-dimensional unit sphere around each point of $P$. These $n$ spheres must cover the unit hypercube since otherwise we can add more points into $P$. Thus one has $n\vol(1b^d)\geq 1$.
|
|
\begin{equation*}
|
|
\begin{aligned}
|
|
n &\geq 1/\vol(1b^d)\\
|
|
&= \frac{\Gamma(d/2+1)}{\pi^{d/2}}\\
|
|
&\geq \sqrt{2\pi/(d/2+1)} (\frac{\sqrt{d}}{\sqrt{2e\pi}})^{d}
|
|
\end{aligned}
|
|
\end{equation*}
|
|
The last line is greater than $(\sqrt{d}/5)^d$ for large enough $d$.
|
|
\end{proof}
|
|
|
|
\begin{exercise}
|
|
Compute clustering radius.
|
|
Let $C$ and $P$ be two given set of points such that $k=|C|$ and $n=|P|$. Define the covering radius of $P$ by $C$ as $r=\max_{p\in P} \min_{c\in C} \norm{p-c}$.
|
|
\begin{enumerate}
|
|
\item find an $O(n+k\log n)$ expected time alg that outputs $\alpha$ such that $\alpha \leq r \leq 10\alpha$.
|
|
\item for prescribed $\varepsilon>0$, find an $O(n+k\varepsilon^{-2}\log n)$ expected time alg that outputs $\alpha$ s.t. $\alpha<r<(1+\epsilon)\alpha$.
|
|
\end{enumerate}
|
|
\end{exercise}
|
|
|
|
|
|
\section*{Not in the book}
|
|
\begin{problem}[$d$-dimensional rectangle stabbing \cite{gaur_constant_2002}]
|
|
Given a set $R$ of $n$ axis-parallel rectangles and a set $\mathcal H$ of axis-parallel $d$ dimensional hyperplanes, find the minimum subset of $\mathcal H$ such that every rectangle is stabbed by at least one hyperplane in the subset.
|
|
\end{problem}
|
|
This problem is NP-hard even for the 2D case. There is a LP rounding method which gives a $d$-approximation for dimension $d$. Let $K_i\subset \mathcal H$ be the set of hyperplanes that are orthogonal to the $i$th axis. For a rectangle $r\in R$, denote by $K_i^r$ the set of hyperplanes in $K_i$ that stab $r$. Consider the following LP.
|
|
|
|
\begin{equation*}
|
|
\begin{aligned}
|
|
\min& & \sum_{H\in \mathcal H} x_H& & & \\
|
|
s.t.& & \sum_{i\in [d]} \sum_{H \in K_i^r} x_H&\geq 1 & &\forall r\in R\\
|
|
& & x_H&\geq 0 & &\forall H\in \mathcal H
|
|
\end{aligned}
|
|
\end{equation*}
|
|
|
|
Let $\set{x^*_H: H\in \mathcal H}$ be the optimal solution to the above LP.
|
|
For each $r$, there must be some $i\in [d]$ such that $\sum_{H \in K_i^r}x^*_H \geq 1/d$. Denote such a set for rectangle $r$ by $K_*^r$.
|
|
Suppose that we find a subset $\mathcal H^{int}\subset \mathcal H$ and define a integral solution $\set{y_H=1}_{H\in \mathcal H^{int}}\cup \set{y_H=0}_{H\notin \mathcal H^{int}}$ such that $\sum_{H\in K_*^r}\geq 1$ for each rectangle $r$. In other words, we restrict the solution such that every rectangle $r$ is stabbed by hyperplanes in $K_*^r$.
|
|
|
|
One nice property of this restriction is that now the problem becomes independent for each dimension. We assign to each rectangle $r$ a dimension $i$ such that $\sum_{H \in K_i^r}x^*_H \geq 1/d$. This assignment indicates a partition $\set{R_i}_{i\in [d]}$ of $R$. We want to solve the following IP for dimension $i\in[d]$.
|
|
|
|
\begin{equation*}
|
|
\begin{aligned}
|
|
IP_i=\min& & \sum_{H\in K_i} x_H& & & \\
|
|
s.t.& & \sum_{H \in K_i^r} x_H&\geq 1 & &\forall r\in R_i\\
|
|
& & x_H&\in \set{0,1} & &\forall H\in K_i
|
|
\end{aligned}
|
|
\end{equation*}
|
|
|
|
Another nice property is that the constraint matrix is TUM since one can sort the hyperplanes in $K_i$ by their intersection with the $i$th axis and see that element $1$'s locate consecutively in each row in the constraint matrix. Hence, the linear relaxation of $IP_i$ (denoted by $LP_i$) is integral and we can solve $IP_i$ in polynomial time.
|
|
|
|
Now we show connections between $x^*$ and solutions of $IP_i$. Let $x^*|_{K_i}$ be the optimal solution to the rectangle stabbing LP restricted to hyperplanes in $K_i$.
|
|
We also have $\sum_{i\in [d]} \opt(IP_i)\leq d \sum_H x^*_H$ since $d x^*|_{K_i}$ is a feasible solution to $LP_i$. Then the $d$-integrality gap follows from the fact that the union of optimal solutions to $IP_i$ is a feasible solution to the rectangle stabbing problem.
|
|
|
|
|
|
|
|
\bibliographystyle{alpha}
|
|
\bibliography{ref}
|
|
|
|
\end{document}
|