James K. Park

MFCS Conference 2002 Conference Paper

Fast Algorithms with Algebraic Monge Properties

• Wolfgang W. Bein
• Peter Brucker
• Lawrence L. Larmore
• James K. Park

Abstract When restricted to cost arrays possessing the sum Monge property, many combinatorial optimization problems with sum objective functions become significantly easier to solve. The more general algebraic assignment and transportation problems are similarly easier to solve given cost arrays possessing the corresponding algebraic Monge property. We show that Monge-array results for two sum-of-edge-costs shortest-path problems can likewise be extended to a general algebraic setting, provided the problems’ ordered commutative semigroup satisfies one additional restriction. In addition to this general result, we also show how our algorithms can be modified to solve certain bottleneck shortest-path problems, even though the ordered commutative semigroup naturally associated with bottleneck problems does not satisfy our additional restriction. We show how our bottleneck shortest-path techniques can be used to obtain fast algorithms for a variant of Hirschberg and Larmore’s optimal paragraph formation problem, and a special case of the bottleneck traveling-salesman problem.

FOCS Conference 1994 Conference Paper

Long Tours and Short Superstrings (Preliminary Version)

• S. Rao Kosaraju
• James K. Park
• Cliff Stein 0001

This paper considers weight-maximizing variants of the classical symmetric and asymmetric traveling-salesman problems. Like their weight-minimizing counterparts, these variants are MAX SNP-hard. We present the first nontrivial approximation algorithms for these problems. Our algorithm for directed graphs finds a tour whose weight is at least 38/63/spl ap/0. 603 times the weight of a maximum-weight tour, and our algorithm for undirected graphs finds a tour whose weight is at least 5/7/spl ap/0. 714 times optimal. These bounds compare favorably with the 1/2 and 2/3 bounds that can be obtained for undirected and directed graphs, respectively, by simply deleting the minimum-weight edge from each cycle of a maximum-weight cycle cover. Our algorithm for directed graphs can be used to improve several recent approximation results for the shortest-superstring problem. >

STOC Conference 1993 Conference Paper

Finding minimum-quotient cuts in planar graphs

• James K. Park
• Cynthia A. Phillips

SODA Conference 1990 Conference Paper

Selection and Sorting in Totally Monotone Arrays

• Dina Kravets
• James K. Park

FOCS Conference 1988 Conference Paper

Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version)

• Alok Aggarwal
• James K. Park

A two-dimensional array A=(a/sub i, j/) is called monotone if the maximum entry in its ith row lies below or to the right of the maximum entry in its (i- 1)-st row. An array A is called totally monotone if every 2*2 subarray (i. e. , every 2*2 minor) is monotone. The notion of two-dimensional totally monotone arrays is generalized to multidimensional arrays, and a wide variety of problems are exhibited involving computational geometry, dynamic programming, VLSI river routing, and finding certain kinds of shortest paths that can be solved efficiently by finding maxima in totally monotone arrays. >