Title: Restricted Track Assignment with Applications* Majid Sarrafzadeh and D. T. Lee Department of Electrical Engineering and Computer Science Northwestern University Evanston, IL 60208 *Supported in part by the National Science Foundation under Grants MIP-8921540 and CCR-8901815. Abstract: Consider a set of intervals $S= \{I_1, I_2, \ldots, I_n\}$, where $I_i=(l_i,r_i), l_i$, and $r_i$ are real numbers, and $l_i < r_i$. We study a restricted track assignment problem (RTAP): if an interval $I_a$ contains another interval $I_b$ then $I_a$ must be assigned to a higher track than $I_b$, and the goal is to minimize the number of tracks used. The problem RTAP is shown to be NP-hard. An approximation algorithm that produces a solution within twice of the optimal is also presented and the bound is shown to be tight. The algorithm runs in $O(n\log n)$ time and requires linear space. The proposed approximation algorithm is employed to solve the problem of finding a maximum-weighted independent set in a circle graph, and related problems. Keywords: Track assignment, circular-arc model, NP-hardness, approximation algorithm. Int'l J. Computational Geometry & Applications, (4,1) March 1994, 53-68.