213611
Covering rectilinear polygons with axis-parallel rectangles
We give an O( 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. 1. Introduction. We consider the problem of covering rectilinear polygons with axis-parallel rectangles. Given a rectilinear polygon P with complexity n (complexity refers to the minimum of the number of vertical edges and the number of horizontal edges in the polygon), this problem requires determining the minimum number of axis-parallel rectangles whose union covers P. The polygon P may have holes in it. Applications. Cheng, Iyengar, and Kashyap (5) showed that this problem has applications to image compression. They claim that representing an image using a rectangle covering of its white pixels gives compression superior to that achieved by quadtrees. It also has applications to printing integrated circuits (9). Hardness. Much effort has gone into determining the computational complexity of this problem. In spite of this, the exact complexity of this problem has remained open for many years and continues to do so. Masek (19) showed that this problem is NP-complete. Later, Culberson and Reckhow (6) used a clever reduction from 3-SAT to show that this is the case even when P has no holes. The next natural question is whether the number of rectangles needed to cover P can be computed approximately. Berman and Dasgupta (2) showed that this problem is MaxSNP-Hard for polygons with holes, ruling out the possibility of a polynomial time approximation scheme. Approximation results. Note that the rectangle covering problem is a special case of the general set covering problem. Therefore, it admits an approximation algorithm with a performance guarantee of O(log n), using the greedy scheme due to Johnson (10) and Lovasz (16). This was the best approximation factor known for the rectangle covering problem until now. Further, it is known that the general set covering problem cannot be approximated any better, modulo constant terms, unless NP = P (17, 18). However, this proof of hardness assumes certain properties about the set system which do not hold for the rectangle covering problem. In this paper, we address the issue of whether the Ω(log n) approximation factor barrier can be broken in polynomial time for the rectangle covering problem. There seem to be only a few examples of nontrivial algorithms breaking this
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.
11502954
Motion generation for formations of robots: A geometric approach
Develops a method for generating smooth trajectories for mobile robots in formation. The problem of trajectory generation is cast in terms of designing optimal curves on the Euclidean group, SE(3). Specifically, the method generates the trajectory that minimizes the total energy associated with the translations and rotations of the robots, while maintaining a rigid formation. When the mobile robots are nonholonomic, trajectories that allow rigid formations to be maintained must satisfy appropriate constraints. An efficient non-iterative algorithm to obtain near-optimal trajectories is described. Finally, the approach is illustrated with examples involving formations of aircrafts.
42935672
Performance Measurement of Main Memory Database Recovery Algorithms Based on Update-in-Place and Shadow Approaches
The authors present a performance study of two main memory database recovery algorithms, one using a shadow approach and the other update-in-place. The results show that in main memory databases, shadow approach performs better than update-in-place. The authors introduce minor improvements to the shadow scheme and show that the modified algorithm does show further performance improvement. >
16578484
On the Complexity of Error Explanation
When a system fails to satisfy its specification, the model checker produces an error trace (or counter-example) that demonstrates an undesirable behavior, which is then used in debugging the system. Error explanation is the task of discovering errors in the system or the reasons why the system exhibits the error trace. While there has been considerable recent interest in automating this task and developing tools based on different heuristics, there has been very little effort in characterizing the computational complexity of the problem of error explanation. 
 
In this paper, we study the complexity of two popular heuristics used in error explanation. The first approach tries to compute the smallest number of system changes that need to be made in order to ensure that the given counter-example is no longer exhibited, with the intuition being that these changes are the errors that need fixing. The second approach relies on the observation that differences between correct and faulty runs of a system shed considerable light on the sources of errors. In this approach, one tries to compute the correct trace of the system that is closest to the counter-example. We consider three commonly used abstractions to model programs and systems, namely, finite state Mealy machines, extended finite state machines and pushdown automata. We show that the first approach of trying to find the fewest program changes is NP-complete no matter which of the three formal models is used to represent the system. Moreover we show that no polynomial factor approximation algorithm for computing the smallest set of changes is possible, unless P = NP. For the second approach, we present a polynomial time algorithm that finds the closest correct trace, when the program is represented by a Mealy machine or a pushdown automata. When the program is represented by an extended finite state machine, the problem is once again NP-complete, and no polynomial factor approximation algorithm is likely.
4677633
A Strategic Modeling Technique for Change Management in Organizations Undergoing BPR
Modern day organizations seek to rationalize, innovate, and adapt to changing environments, and circumstances as part of Business Process Reengineering (BPR) efforts. Irrespective of the process reengineering program selected, and the technique used to model, BPR brings with it the issues of organizational, and process changes, which involves managing organizational changes (also called “change management”). Change management is non-trivial, as organizational changes are difficult to accomplish. Though some attempt has been made to model change management in enterprise information systems using conventional conceptual modeling techniques, they have just addressed “what” a change process is like, and they don’t address “why” the process is the way it is. Our approach is novel in the sense that it presents an actor-dependency-based 5-phased technique for analyzing, and modeling early-phase requirements of change management that provides the motivations, intents, and rationales behind activities.
14506171
Optimal constrained graph exploration
We address the problem of exploring an unknown graph <i>G</i> = (<i>V</i>, <i>E</i>) from a given start node <i>s</i> with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length <i>l</i>, then the robot must remain within distance <i>l</i> from the start node <i>s</i>. In the second variation, a fuel tank of limited capacity forces the robot to return to <i>s</i> after traversing <i>C</i> edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in <i>&Ogr;</i>(¦<i>E</i>¦) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a <i>&Ogr;</i>(¦<i>E</i>¦) algorithm. This improves on the previous best known bound of <i>&Ogr;</i>(¦<i>E</i>¦ + ¦<i>V</i>¦log <sup>2</sup>¦<i>V</i>¦) in [4]. Since the lower bound for the graph exploration problems is ¦<i>E</i>¦, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3].