47057582
Covering Rectilinear Polygons with Axis-Parallel Rectangles
We give an $O(\sqrt{\log n})$ factor approximation algorithm for covering a rectilinear polygon with holes using axis-parallel rectangles. This is the first polynomial time approximation algorithm for this problem with an $o(\log n)$ approximation factor.
16892281
The algorithmics of folding proteins on lattices
It should be possible to predict the fold of a protein into its native conformation, once we are given the sequence of the constituent amino acids. This is known as the protein structure prediction problem and is sometimes referred to as the problem of deciphering the second half of the genetic code. While large proteins fold in nature in seconds, computational chemists and biologists have found that folding proteins to their minimum energy conformations is a challenging unsolved optimization problem. Computational complexity theory has been useful in explaining, at least partially, this (Levinthal's) paradox. The pedagogic cross-disciplinary survey by Ngo, Marks and Karplus (Computational Complexity, Protein Structure Prediction and the Levinthal Paradox, Birkhauser, Basel, 1994) provides an excellent starting point for nonbiologists to take a plunge into the problem of folding proteins. Since then, there has been remarkable progress in the algorithmics of folding proteins on discrete lattice models, an account of which is presented herein.
38425944
Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints
We present polylogarithmic approximations for the R|prec|Cmax and R|prec|∑jwjCj problems, when the precedence constraints are “treelike” – i.e., when the undirected graph underlying the precedences is a forest. We also obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment – this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion+dilation”, as in other job shop scheduling approaches. The first step in our algorithm for the R|prec|Cmax problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random delays technique of Leighton, Maggs and Rao to the case of trees. For the weighted completion time, we show a certain type of reduction to the makespan problem, which dovetails well with the lower bound we employ for the makespan problem. For the special case of chains, we show a dependent rounding technique which leads to improved bounds on the weighted completion time and new bicriteria bounds for the flow time.
16403985
Human robot interaction: application to smart wheelchairs
Addresses the problem of human robot interaction with application to the design of assistive devices. We describe the design and development of a prototype of a smart wheelchair that can be commanded by a rider. Specifically, we focus on (a) the vision-based human interaction interface; (b) the suite of sensors on the chair, and (c) the software architecture and the control algorithms used to control the chair.
7638167
Congruences for Visibly Pushdown Languages
We study congruences on words in order to characterize the class of visibly pushdown languages (Vpl), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a Vpl. We then study the problem of finding canonical minimal deterministic automata for Vpls. Though Vpls in general do not have unique minimal automata, we consider a subclass of VPAs called k-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched Vpls do indeed have unique minimal k-module single-entry automata. We also give a polynomial time algorithm that minimizes such k-module single-entry VPAs.
30844152
Multiple cooperating mobile manipulators
The main goal of the paper is to present a framework and basic control algorithms for coordinating a small team of robots in tasks that involve grasping large objects and transporting them in a two-dimensional environment with obstacles. Each robot consists of a mobile platform and an arm. Some arms are passive while others are active. Our previous work (1998) addressed the manipulator design, the architecture, and the communication between robots. In this paper we address the control of the manipulators, the coordination between the platforms for a team of two or three cooperating robots, and the handling of flexible large objects.
40462435
A concurrency control mechanism based on extendible hashing for main memory database systems
A non-preemptive deadlock-free concurrency control mechanism based on extendible hashing has been presented for main memory database system. The algorithm makes use of the verification process of the optimistic concurrency control algorithm and two-phase locking policy to manage concurrent operations on sharable data. We also present a comparison of our algorithm with other two-phase locking mechanisms and show that our algorithm is more robust, easier to implement and provides a higher degree of concurrency than other algorithms on extendible hash file.