Abstract
We propose approximation algorithms for some facility location and
graph partitioning problems. Since most of the practically
important facility location and graph partitioning problems are
NP-Hard, the researchers are interested in approximation
algorithms of these problems. The major part of this thesis
presents approximation algorithms with better approximation ratio
for some already established important problems and the remaining
part proposes new problems with clear practical motivations.
We present a 8.29 factor LP-rounding based approximation algorithm
for the connected facility location problem which improves the
previous factor 8.55. Our algorithm gives a 7.00 approximation
ratio for the special case of the connected facility location
problem when all facilities have equal opening cost. We also give
a primal-dual based approximation algorithm for the connected
facility location problem with 6.55 approximation ratio. For the
lower bounded facility location problem we give a 322 + $\epsilon$
factor approximation algorithm which improves the previous factor
which is 558+$\epsilon$.
We study the minimum geometric mean layout (MGML) problem. In an
instance of the MGML problem we are given a graph $G=(V, E)$. The
objective is to find a one-to-one mapping $f:V \rightarrow \{1, 2,
..., |V|\}$ such that the cost $\sum_{\{u,v\} \in E} \log
(|f(u)-f(v)|)$ is minimized. Given graph $G=(V, E)$ representing a
polygonal mesh and one-to-one function $f: V \rightarrow \{1, 2,
..., |V|\}$ as the layout of the mesh in the main memory, Yoon and
Lindstrom [51] have shown that the number
of cache misses while accessing the mesh in the data layout has a
high linear correlation with the geometric mean of arc
lengths: $2^{\frac{1}{|E|}\sum_{\{u,v\} \in E} \log
(|f(u)-f(v)|)}$. Thus, getting a good solution to the minimum
geometric mean layout problem implies getting a good mesh
layout in terms of the number of cache misses for common computer
graphics applications. We have given a constant factor
approximation algorithm for the MGML for bounded-degree planar
graphs. Since in most of the cases, a polygonal mesh used in
practice is a bounded-degree planar graph, this result implies
that we can find a mesh layout such that while accessing the mesh
data from this layout, the number of cache misses in two level
memory hierarchy model is significantly smaller as compared to
that while using arbitrary layout.
We study the Weighted $t$-Uniform Sparsest Cut and some other
related problems. In an instance of the Weighted $t$-Uniform
Sparsest Cut problem, a parameter $t$ and an undirected graph $G =
(V, E)$ with edge-weights $w: E \rightarrow \mathbb R_{\geq 0}$
and vertex-weights $\eta : V \rightarrow \mathbb R_{+} $ are
given. The goal is to find a vertex set $S \subseteq V$ of size at
most $t$ such that $w(S, V \backslash S) / \eta(S)$ is minimized,
where $w(S, V \backslash S)$ is the total weight of the edges with
exactly one endpoint in $S$ and $\eta(S) = \sum_{v \in S}
\eta(v)$. For this problem we present a Linear Programming based
deterministic bicriteria approximation algorithm which, for any
constant $\epsilon > 0$, finds a set $S$ of size at most
$(1+\epsilon)t$ such that $w(S, V \backslash S)/\eta(S)$ is at
most $O(\log t) \times OPT $, where $OPT$ is the optimal cost. For
the Weighted $t$-Sparsest Cut problem, to the best of our
knowledge, our algorithm is the first one which gives an
approximation factor independent of $n$. When $t = n^{o(1)}$, our
algorithm gives better approximation factor than the current best
bicriteria approximation factor which is $(O(\sqrt{\log n \log
(n/t)}), 1 + \epsilon)$ [7]. For the special case
when every vertex has equal weight, our algorithm gives better
approximation factor than that of any existing bicriteria
approximation algorithm when $t = \omega(\log n \log \log n)$ and
$t = n^{o(1)}$.
Our approximation algorithm for the Weighted $t$-Uniform Sparsest
Cut problem can be used to get approximation algorithms for the
Weighted $\rho$-Unbalanced Cut problem and the Min-Max
$k$-Partitioning problem. For the Weighted $\rho$-Unbalanced Cut
problem, our algorithm gives better approximation factor than that
given by any exiting algorithm when $\rho n = n^{o(1)}$ and for
the Min-Max $k$-Partitioning problem, when $k \geq n^{1 - o(1)}$
our algorithm gives better approximation factor than the current
best one.
본 논문은 몇 가지 시설 배치(facility location) 및 그래프 분할(graph partitioning) 문제들에 대한 근사 알고리즘을 제안한다.
실질적으로 중요한 시설 배치 문제들과 그래프 분할 문제들의 대부분은 NP-Hard에 속하기 때문에 연구자들은 이 문제들에 대한 근사 알고리즘에 관심을 가져왔다.
본 논문에서는 몇 몇의 이미 확립된 중요한 문제들에 대해 더 좋은 근사 비율(approximation ratio)을 갖는 근사 알고리즘을 제안하며,
또한 명확하고 실질적인 동기부여를 갖는 새로운 문제들을 제안한다.
본 논문은 연결 시설 배치 문제(connected facility location problem)에 대해 8.29 근사 비율을 갖는 LP-rounding에 기반한 근사 알고리즘을 제안하며,
이것은 기존의 8.55 근사 비율을 개선하는 것이다.
모든 시설들이 동일한 개설비용(opening cost)을 갖는 특별한 경우, 제안된 알고리즘은 연결 시설 배치 문제에 대해 7.00 근사 비율을 보여준다.
본 논문은 또한 연결 시설 배치 문제에 대해 6.55 근사 비율을 갖는 원본쌍대(primal-dual) 기반의 근사 알고리즘을 제안한다.
하계(lower bounded) 시설 배치 문제에 대해서는 322+$\epsilon$ 근사 알고리즘을 제안하며 이것은 기존의 558+$\epsilon$ 근사 비율을 개선하는 것이다.
본 논문은 최소 기하 평균 배치 문제(minimum geometric mean layout\\ (MGML))를 다룬다.
MGML문제는 주어진 그래프 $G=(V, E)$에 대해, 비용 $\sum_{\{u,v\} \in E}\log(|f(u)-f(v)|)$을 최소로 만드는 일대일(one-to-one) 매핑
$f:V \rightarrow \{1, 2,..., |V|\}$을 찾는 것을 목표로 한다.
Yoon과 Lindstrom [51]은 다각형 메쉬(polygonal mesh)를 나타내는 그래프 $G=(V, E)$와 주 기억장치(main memory)에서 메쉬의 배치(layout)로서
일대일 함수 $f: V \rightarrow \{1, 2,..., |V|\}$가 주어졌을 때, 데이터 배치에 있는 메쉬에 접근하는 동안의 캐시 실패(cache misses)의 횟수는
호 길이(arc length)의 기하 평균\\ $2^{\frac{1}{|E|}\sum_{\{u,v\} \in E} \log(|f(u)-f(v)|)}$과 높은 선형 상관관계(linear correlation)를 갖는다는 것을 보여주었다.
따라서, 최소 기하 평균 배치 문제에 대한 좋은 해를 구하는 것은 일반적인 컴퓨터 그래픽스 응용들에 대한 캐시 실패 횟수의 관점에서 보면
좋은 메쉬 배치(mesh layout)를 구하는 것을 의미한다고 볼 수 있다.
본 논문은 유계 자유도를 갖는 평면 그래프(bounded degree planar graph)에 대한 MGML에 대해 상수적(constant factor) 근사 알고리즘을 제안한다.
대부분의 경우, 실질적으로 사용되는 다각형 메쉬는 유계 자유도를 갖는 평면 그래프이기 때문에,
이 결과는 이러한 배치로부터 메쉬 데이터에 접근하는 동안 두 단계의 메모리 계층 모델(two level memory hierarchy mode)에서의 캐시 실패의 횟수가
임의의 배치를 사용하는 동안의 그것과 비교할 때 상당히 적도록 하는 메쉬 배치를 찾을 수 있다는 것을 의미한다.
본 논문은 Weighted $t$-Uniform Sparsest Cut문제와 몇 가지 다른 관련문제들에 대한 연구를 포함한다.
Weighted $t$-Uniform Sparsest Cut문제에서는 파라미터 $t$와 에지-가중치(edge-weights) $w: E \rightarrow \mathbb R_{\geq 0}$와 정점-가중치(vertex-weights)
$\eta : V \rightarrow \mathbb R_{+}$를 갖는 무방향(undirected) 그래프 $G=(V, E)$가 주어진다.
$w(S, V \backslash S)$가 $S$에서 정확히 하나의 끝점(endpoint)을 갖는 에지 들의 전체 가중치이고
$\eta(S)$는 $\eta(S) = \sum_{v \in S}\eta(v)$와 같이 정의될 때, 문제의 목적은 $w(S, V \backslash S) / \eta(S)$가 최소가 되도록
최대 $t$의 크기를 갖는 정점들의 집합 $S \subseteq V$을 찾는 것이다.
이 문제에 대해 본 논문은 선형 계획법(linear programming)에 기반한 결정론적 bicriteria근사 알고리즘을 제안한다.
이 알고리즘은 $OPT$가 최적비용이라고 할 때 $w(S, V \backslash S)/\eta(S)$가 최대 $O(\log t) \times OPT $가 되도록
어떤 상수 $\epsilon > 0$에 대해 최대 $(1+\epsilon)t$ 크기를 갖는 집합 $S$를 찾는다.
알고 있는 한, Weighted $t$-Sparsest Cut 문제에 대해, 이 알고리즘은 $n$에 독립적인 근사 비율을 제공하는 최초의 알고리즘이다.
$t = n^{o(1)}$인 경우에, 제안된 알고리즘은 현재 최고의 bicriteria 근사 비율 $(O(\sqrt{\log n \log(n/t)}), 1 + \epsilon)$ [7] 보다 더 좋은 근사 비율을 제공한다.
모든 정점이 동일한 가중치를 갖는 특별한 경우에, 제안된 알고리즘은 $t = \omega(\log n \log \log n)$이고 $t = n^{o(1)}$일 때
기존의 어떤 bicriteria 근사 알고리즘보다도 더 좋은 근사 비율을 제공한다.
Weighted $t$-Uniform Sparsest Cut문제에 대해 본 논문에서 제안된 근사 알고리즘은
Weighted $\rho$-Unbalanced Cut문제와 Min-Max $k$-Partitioning문제에 대한 근사 알고리즘을 구하는데 사용될 수 있다.
Weighted $\rho$-Unbalanced Cut문제에 대해서, 제안된 알고리즘은 $\rho n = n^{o(1)}$인 경우 기존의 어떤 알고리즘보다도
더 좋은 근사 비율을 제공하며, Min-Max $k$-Partitioning문제에 대해서는 $k \geq n^{1 - o(1)}$ 경우에 현재의 최고의 알고리즘보다 더 좋은 근사 비율을 제공한다.
