서지주요정보
Approximation algorithms for facility location and graph partitioning problems = 시설 배치와 그래프 분할 문제에 대한 근사 알고리즘
서명 / 저자 Approximation algorithms for facility location and graph partitioning problems = 시설 배치와 그래프 분할 문제에 대한 근사 알고리즘 / Mohammad Khairul Hasan.
저자명 Mohammad Khairul Hasan ; MK Hasan
발행사항 [대전 : 한국과학기술원, 2013].
Online Access 원문보기 원문인쇄

등록번호

8024894

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 13010

도서상태

이용가능

반납예정일

#### 초록정보

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)}$ 경우에 현재의 최고의 알고리즘보다 더 좋은 근사 비율을 제공한다.

#### 서지기타정보

청구기호 {DCS 13010 v, 67 p. : 삽도 ; 30 cm 영어 저자명의 한글표기 : MK Hasan 지도교수의 영문표기 : Sung-Yong Shin 지도교수의 한글표기 : 신성용 공동지도교수의 영문표기 : Kyung-Yong Chwa 공동지도교수의 한글표기 : 좌경룡 수록잡지명 : "A 6.55 factor primal-dual approximation algorithm for the connected facility location problem". Journal of Combinatorial Optimization, v.18 no.3, pp.258-271(2009) 수록잡지명 : "Approximation algorithms for connected facility location problems". Journal of Combinatorial Optimization, v.16 no.2, pp.155-172(2008) 학위논문(박사) - 한국과학기술원 : 전산학과, References : p. 62-65 Approximation Algorithm Graph Partitioning Facility Location 근사 알고리즘 그래프 파티션 시설 배치
QR CODE