Chul E. Kim

ICRA Conference 1985 Conference Paper

Movement coordination for single-track robot systems

• Michael A. Langston
• Chul E. Kim

We consider problems associated with the coordination of movement within a multiple robot system in which all motion is restricted to a single track. Our objective is to minimize the reconfiguration time, that is, the total time required to move a collection of robots from an initial to a goal configuration. We show that various models give rise to a wide range of problem complexities. For these problems we design and analyze optimization and approximation strategies.

STOC Conference 1984 Conference Paper

Digital Disks and a Digital Compactness Measure

• Chul E. Kim
• Timothy A. Anderson

STOC Conference 1981 Conference Paper

Digital Straightness and Convexity (Extended Abstract)

• Chul E. Kim
• Azriel Rosenfeld

STOC Conference 1976 Conference Paper

A Useful Device for Showing the Solvability of Some Decision Problems

• Oscar H. Ibarra
• Chul E. Kim

FOCS Conference 1976 Conference Paper

Approximation Algorithms for some Routing Problems

• Greg N. Frederickson
• Matthew S. Hecht
• Chul E. Kim

Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling Salesman problem, the Chinese Postman problem, and the Stacker-Crane problem, for which a minimax solution is sought. This heuristic has a bound of e + 1 - 1/k, where e is the bound for the corresponding 1-person algorithm.

TCS Journal 1976 Journal Article

Finite automata with multiplication

• Oscar H. Ibarra
• Sartaj K. Sahni
• Chul E. Kim

A finite automaton with multiplication (FAM) is a finite automaton with a register which is capable of holding any positive rational number. The register can be multiplied by any of a fixed number of rationals and can be tested for value 1. Closure properties and decision problems for various types of FAM's (e. g. two-way, one-way, nondeterministic, deterministic) are investigated. In particular, it is shown that the languages recognized by two-way deterministic FAM's are of tape complexity log n and time complexity n 3. Some decision problems related to vector addition systems are also studied.