Augmenting Trees to Meet Biconnectivity and Diameter Constraints

Given a graph G=(V,E) and a positive integer D , we consider the problem of finding a minimum number of new edges E' such that the augmented graph G'=(V,E\cup E') is biconnected and has diameter no greater than D. In this note we show that this problem is NP-hard for all fixed D , by employing a reduction from the DOMINATING SET problem. We prove that the problem remains NP-hard even for forests and trees, but in this case we present approximation algorithms with worst-case bounds 3 (for even D ) and 6 (for odd D ). A closely related problem of finding a minimum number of edges such that the augmented graph has diameter no greater than D has been shown to be NP-hard by Schoone et al. [21] when D=3 , and by Li et al. [17] when D=2. Received April 19, 1999; revised June 5, 2001.     

A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.     

Proactive resource allocation for asynchronous real-time distributed systems in the presence of processor failures

We present two proactive resource allocation algorithms, RBA^*-FT and OBA-FT, for fault-tolerant asynchronous real-time distributed systems. The algorithms consider an application model where task timeliness is specified by Jensen's benefit functions and the anticipated application workload during future time intervals is described by adaptation functions. In addition, we assume that reliability functions of processors are available a priori. Given these models, our objective is to maximize aggregate task benefit and minimize aggregate missed deadline ratio in the presence of processor failures. Since determining the optimal solution is computationally intractable, the algorithms heuristically compute sub-optimal resource allocations, but in polynomial time. Experimental results reveal that RBA^*-FT and OBA-FT outperform their non-fault-tolerant counterparts in the presence of processor failures. Furthermore, RBA^*-FT performs better than OBA-FT, although OBA-FT incurs better worst-case and amortized computational costs. Finally, we observe that both algorithms robustly withstand errors in the estimation of anticipated failures.     

On finding optimal and near-optimal lineal spanning trees

The search for good lineal, or depth-first, spanning trees is an important aspect in the implementation of a wide assortment of graph algorithms. We consider the complexity of findingoptimal lineal spanning trees under various notions of optimality. In particular, we show that several natural problems, such as constructing a shortest or a tallest lineal tree, are NP-hard. We also address the issue of polynomial-time, near-optimization strategies for these difficult problems, showing that efficient absolute approximation algorithms cannot exist unlessP = NP.This author's research was supported in part by the Sandia University Research Program and by the National Science Foundation under Grant M IP-8603879.This author's research was supported in part by the National Science Foundation under Grants ECS-8403859 and MIP-8603879.     

Lyapunov analysis of the approximate motion equations of flexible structures

In this paper, the effectiveness of the approximate motion equations of a flexible structure, obtained by the RitzKantorovich method, is analysed by using Lyapunov functions. The analysis, which is restricted to the case of a single flexible beam for the sake of simplicity, is carried out under the assumption that a partial dissipation is present, affecting only the first degrees of freedom of the system. By means of suitable Lyapunov functions, an overbounding estimate of the quadratic approximation error is determined as a decreasing function of the approximation order. The analysis is completed by considering the two ‘extreme’ cases: the theoretical absence of dissipation and the presence of structural dissipation, affecting all the infinite degrees of freedom.     

An algorithm for the three-dimensional packing problem with asymptotic performance analysis

The three-dimensional packing problem can be stated as follows. Given a list of boxes, each with a given length, width, and height, the problem is to pack these boxes into a rectangular box of fixed-size bottom and unbounded height, so that the height of this packing is minimized. The boxes have to be packed orthogonally and oriented in all three dimensions. We present an approximation algorithm for this problem and show that its asymptotic performance bound is between 2.5 and 2.67. This result answers a question raised by Li and Cheng [5] about the existence of an algorithm for this problem with an asymptotic performance bound less than 2.89. This research was partially supported by FAPESP (proc. 93/0603-1) and by CNPq/ProTeM-CC, project ProComb (proc. 680065/94-6).     

Development and implementation of a NURBS curve motion interpolator

This paper deals with the issues of development and implementation of a real-time NURBS interpolator for a six-axis robot. Using an open-architecture controller system as a testbed, a real-time NURBS curve interpolator was developed, implemented and tested. Sample runs were conducted with the resulting trajectories measured in real-time during robot motion. The resulting trajectories are analyzed, discussed and compared with those from a commonly used point-to-point approximation technique. The real-time NURBS curve interpolator's feasibility, advantages and related issues are also discussed.     

Nonnegative integral subset representations of integer sets

We consider an integer-subset representation problem motivated by a medical application in radiation therapy. We prove NP-completeness, derive nontrivial bounds, and report on the performance of a greedy heuristic.     

Approximation algorithms for minimizing segments in radiation therapy

Intensity modulated radiation therapy (IMRT) is one of the most effective modalities for modern cancer treatment. The key to successful IMRT treatment hinges on the delivery of a two-dimensional discrete radiation intensity matrix using a device called a multileaf collimator (MLC). Mathematically, the delivery of an intensity matrix using an MLC can be viewed as the problem of representing a non-negative integral matrix (i.e., the intensity matrix) by a linear combination of certain special non-negative integral matrices called segments, where each such segment corresponds to one of the allowed states of the MLC. The problem of representing the intensity matrix with the minimum number of segments is known to be NP-complete. In this paper, we present two approximation algorithms for this matrix representation problem. To the best of our knowledge, these are the first algorithms to achieve non-trivial performance guarantees for multi-row intensity matrices.     

Uniform modeling of parameter dependent nonlinear systems

This paper addresses the problem of approximating parameter dependent nonlinear systems in a unified framework. This modeling has been presented for the first time in the form of parameter dependent piecewise affine systems. In this model, the matrices and vectors defining piecewise affine systems are affine functions of parameters. Modeling of the system is done based on distinct spaces of state and parameter, and the operating regions are partitioned into the sections that we call ’multiplied simplices’. It is proven that this method of partitioning leads to less complexity of the approximated model compared with the few existing methods for modeling of parameter dependent nonlinear systems. It is also proven that the approximation is continuous for continuous functions and can be arbitrarily close to the original one. Next, the approximation error is calculated for a special class of parameter dependent nonlinear systems. For this class of systems, by solving an optimization problem, the operating regions can be partitioned into the minimum number of hyper-rectangles such that the modeling error does not exceed a specified value. This modeling method can be the first step towards analyzing the parameter dependent nonlinear systems with a uniform method.