Design and analysis of approximation algorithms for facility location problems has been an active area of research in operations research, theory of computation, and telecommunication network for the past decade. Facility location problem (FLP) starts with clients and facilities given. Each facility has facility opening cost. The objective of an FLP is to open a subset of facilities and connect each client to an open facility so that the sum of connection cost and facility opening cost is minimized. Most of the facility location problems that we deal with in this thesis are NP-hard problems. We focus on approximation algorithms that guarantee a solution within constant factor times the value of an optimal solution for FLPs. In approximation algorithms, it is crucial to get a tight lower bound in polynomial time, for it helps reducing an approximation factor. Then, we construct a solution that guarantees a constant factor approximation from the lower bound. We use two types of methods, namely, LP-based and non-LP-based in our approximation algorithms. An LP-solution is known to provide a lower bound for an optimal cost.
We present LP-based improved approximation algorithms on connected facility location, hybrid wireless facility location, priority facility location, and facility location with service installation costs, all of which have LP-formulations. In detail, we use primal-dual methods for connected facility location problem and hybrid wireless facility location that require connection of open facilities via a Steiner tree. For priority facility location and facility location with service installation costs whose clients need services, we use a randomized algorithm that combines an LP-solution and a bi-factor solution. By using non-LP-based methods, we present approximate and exact algorithms on online facility location, minimum diameter Steiner tree, and quake detector location that need aggregation of clients for solving the problems. We improve either constant approximation factor or time complexity for the problems.
In a connected facility location problem [48] of connecting open facilities via a Steiner tree, we give an improved combinatorial primal-dual algorithm. We use dual increment for paying for facility opening cost, then for gathering clients. By opening facilities incrementally, we remove the step of selecting independent locations. For a hybrid wireless facility location problem that combines wireless base station and wired core networks, we give constant factor approximation algorithms. We use dual increment for paying for facilities. Then, we connect the open facilities by using an approximate Steiner tree. For a priority facility location problem [47] and facility location with service installation costs [46], where each client requires service, we give simple randomized algorithms that give current best approximation factor. We use LP-rounding solution with high probability. With low probability, we use a bifator solution. By doing this, we can decrease expected connection cost. In an online facility location problem, demands arrives one by one. We determine whether to open a new facility or not when a demand arrives. If we open a new facility, we reassign the arrived demands. For an online facility location problem on star graphs, we give a constant competitive algorithm. We use a double augmenting argument to prove the competitiveness. For a minimum diameter Steiner tree problem on general graphs, where the objective is to minimize the diameter of a Steiner tree of given terminals, we present a polynomial time exact algorithm. We prove that the shortest path tree from a Steiner 1-center gives exact solution. Finally, we formulate a quake detector location problem that locates detectors and detects the quake origin by using detection times of the quake, and we give a polynomial time exact algorithm on trees by using a decomposition method. For all problems we present in this thesis, we guarantee constant factor approximations or exact algorithms. In addition, our algorithm guarantee the current best factor approximations or the current best deterministic algorithms.
지난 10여 년간 시설 배치 문제에 대한 근사알고리즘 연구는 급속하고 방대하게 이루어졌다. LP-rounding, Primal-Dual 방법론, Local search 등 다양한 방법론이 시설 배치 문제에 대한 상수 근사알고리즘들을 개발하고 개선시키기 위해 사용되었다. 상수 근사 알고리즘이란 효율적인 시간 내에 최적해의 상수 배 이내의 해를 보장해 주는 알고리즘이다. 연결시설배치문제(ConFL)에 대해서 기존의 LP-rounding 알고리즘을 확장하고 무작위성(randomization)을 추가하여 기존의 Swamy 연구그룹[48]에 의해 제시된 근사비 8.55를 개선하는 8.29-근사알고리즘을 발견하고 분석하였다[23]. 이후 Eisenbrand 연구그룹(2008)에 의해 근사비 4.29의 결정근사알고리즘이 개발되었지만, 이 알고리즘은 결정 알고리즘으로 만들기 위해 무작위 알고리즘을 결정화(derandomization)하는 과정에서 지수(exponential) 크기의 LP를 해결해야하므로 비효율적인 측면이 강하다. 이 부분을 개선하기 위해 본 논문에서는 Primal-Dual 방법론에 기반한 조합적인 6.55-근사알고리즘을 개발한다[30]. 유무선망을 연결하는 유무선 복합 시설배치 문제(HWFLP)를 설계하고 이 문제에 대한 Primal-Dual 방법론에 기반한 4.55-근사알고리즘을 개발하고 분석한다. 시설 배치 문제에 대한 일반적인 무작위 알고리즘을 개발하여 우선순위시설배치문제(PFLP), 서비스설치시설 배치문제(FLSICP)에 적용하여 기존의 알고리즘보다 개선된 근사비를 갖는 근사알고리즘을 개발한다. 온라인 시설 배치 문제(OFLP)란 고객들이 한꺼번에 주어지는 것이 아니라 시간이 지남에 따라 주어질 때, 시설들을 배치하여 고객들을 할당하는 문제이다. 스타(star) 그래프 위에서 온라인 시설배치 문제에 대해 4-컴페터티브한 온라인 알고리즘을 개발한다. 지름을 최소화하는 스타이너 트리 문제(MDST)에 대해 최적의 해의 특성을 규명한 후 효율적인 시간내에 최적의 해를 찾는 알고리즘을 개발한다. 그래프 상에 파(quake)가 발생하는 경우에 이를 탐지하기 위해 최소의 탐지기를 설치하고 설치된 탐지기를 바탕으로 파의 발생 위치(quake origin)을 찾는 문제(QDLP)를 설계하고 트리 상에서 위 문제에 대한 O(n) 선형시간 알고리즘을 개발하고 분석한다.
