Browsing by Author "Kim, Joon-Mo"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    A Polynomial Time Approximation Scheme for the problem of Interconnecting Highways
    (2000-11-28) Cheng, Xiuzhen; Kim, Joon-Mo; Lu, Bing
    The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework in [2]. For every fixed c>1 and given any n line segments in the plane, a randomized version of the scheme finds a (1+1/c)-approximation to the optimal cost in O(n o(c)log n) time.
  • Thumbnail Image
    Item
    A PTAS for the Grade of Service Steiner Minimum Tree Problem
    (2001-12-26) Kim, Joon-Mo; Cardei, Mihaela
    In this paper, we present the design of a PTAS(Polynomial Time Approximation Scheme) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. The previous research has focused on geometric analyses and different approximation algorithms were proposed. But having the PTAS, which provides a near-optimal solution, would be the conclusion for an optimization problem. This problem has some important applications. In the Network Design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions always provide paths with enough communication capacities between any two sites, with the least network construction costs. GOSST problem also has applications in transportation, for road constructions and some more potential uses in CAD in terms of interconnecting the elements on a plane such that to provide enough flux between any two elements.
  • Thumbnail Image
    Item
    A Quadratic Integer Programming with Application in Chaotic Mappings of Complete Multipartite Graphs
    (2000-10-02) Fu, Hung-Lin; Shiue, Chin-lin; Cheng, Xiuzhen; Du, Ding-Zhu; Kim, Joon-Mo
    Let alpha be a permutation of V(G) of a connected graph G. Define the total relative displacement of alpha in G by where dG(x,y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of deltaalpha(G) among all permutations of V(G) and the permutation which realizes pi*(G) is called a chaotic mapping of G. In this paper, we study the chaotic mappings of complete multipartite graphs. The problem will reduce to a quadratic integer programming. We characterize its optimal solution and present an algorithm running in O(n5log n) time where n is the total number of vertices in a complete multipartite graph.
  • Thumbnail Image
    Item
    Approximation ratio 2 for the Minimum number of Steiner Points
    (2001-12-10) Kim, Joon-Mo
    This paper provides an approximation algorithm for STP-MSP(Steiner Tree Problem with Minimum number of Steiner Points). Because it seems to be impossible to have a PTAS(Polynomial Time Approximation Schemes), which gives the near optimal solutions, for the problem, the algorithm of this paper is an alternative that has the approximationratio 2 with a polynomial run time. The importance of this paper is the potential to solve other related unsolved problems. The idea of this paper is to distribute the error allowance over the problem instance so that we may reduce the run time to polynomial bound out of infintely many cases.