DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Chwa, Kyung-Yong | - |
dc.contributor.advisor | 좌경룡 | - |
dc.contributor.author | Hasan, Mohammad Khairul | - |
dc.contributor.author | 하산, 카이룰 | - |
dc.date.accessioned | 2011-12-13T06:06:08Z | - |
dc.date.available | 2011-12-13T06:06:08Z | - |
dc.date.issued | 2006 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=260087&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/34734 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 전산학전공, 2006.8, [ iv, 22 p. ] | - |
dc.description.abstract | We study the Connected Facility Location problems. We are given a connected weighted graph G = (V,E) with non-negative edge cost $C_e$ for each edge $e \in E$, a set of clients $D \subseteq V$ such that each client $j \in D$ has positive demand $d_j$ and a set of facilities $F \sebseteq V$ each has non-negative opening cost $f_i$ and capacity to serve all client demands. The objective is to open a subset of facilities, say $\^{F}$, connect each client $j \in D$ to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost $\sum_{i \in \^{F}}f_i + \sum_{j \in D}d_jc_i(j)j + M \sum_{e \in T}c_e$ is minimized, where $M \geq 1$ be an input parameter. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55. We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | approximation algorithm | - |
dc.subject | Facility-location | - |
dc.subject | primal-dual algorithm | - |
dc.subject | Primal-dual 알고리즘 | - |
dc.subject | 근사 알고리즘 | - |
dc.subject | 시설-배치 | - |
dc.title | Improved approximation algorithm for connected facility locatin problems | - |
dc.title.alternative | 연결 시설 배치 문제에 관한 개선된 근사 알고리즘 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 260087/325007 | - |
dc.description.department | 한국과학기술원 : 전산학전공, | - |
dc.identifier.uid | 020044369 | - |
dc.contributor.localauthor | Chwa, Kyung-Yong | - |
dc.contributor.localauthor | 좌경룡 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.