42704581
An Improved Approximation Algorithm for Uncapacitated Facility Location Problem with Penalties
In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm first enhances the primal-dual method for the UFLWP problem [3] so that outliers can be recognized more efficiently, and then applies a local search heuristic to further reduce the cost for serving those non-rejected clients.
11706299
An Efficient Algorithm for Determining 3-D Bi-plane Imaging Geometry
Biplane projection imaging is one of the primary methods for imaging and visualizing the cardiovascular systems in medicine. A key problem in such a technique is to determine the imaging geometry (i.e., the rotation and translation) of two projections so that the 3-D structure can be accurately reconstructed. Based on interesting observations and efficient geometric techniques, we present in this paper a new algorithmic solution for this problem. Comparing with existing optimization-based approaches, our technique yields better accuracy, has bounded execution time, and thus is more suitable for on-line applications. Our technique can easily deal with outliers for further improving the accuracy.
9722420
Power domination in block graphs
The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 2002, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number γp(G) of a graph G is the minimum cardinality of a power dominating set of G. This problem was proved NP-complete even when restricted to bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for solving the power domination problem in block graphs. As an application of the algorithm, we establish a sharp upper bound for power domination number in block graphs and characterize the extremal graphs.
9063634
Hierarchical multiresolution reconstruction of shell surfaces
We present an adaptive, hierarchical Hh-multiresolution reconstruction algorithm to model shell surface objects from a matched pair of triangulated surfaces. Shell surfaces are an interval of contours of trivariate functions with prismatic support. In the H-direction, a hierarchical representation of the scaffold is constructed. For any adaptively extracted scaffold from the hierarchy, a sequence of functions in the h-direction (regularly subdivided mesh) is constructed so that their contours approximate the input shell to within a given error e. The shell surfaces can be made to capture sharp curve creases on the shell while being C1 smooth everywhere else. Using an interval of iso-contours of smooth trivariate spline functions, rather than a pair of inner and outer surface splines, one avoids the need for interference checks between the inner and outer surface boundaries.
30893886
Delay Defect Characterization Using Low Voltage Test
For nanometer designs, many subtle defects lead to excessive delays in signal paths that cause reliability concerns. Traditional test-based diagnosis methods can only identify the failing nodes without the capability to tell the defect nature behind the observed delay faults. This differentiation is important for gathering accurate defect statistics for process improvement during yield ramp-up. In this paper we presented an effective delay defect analysis methodology that can quickly categorize the delay defects into either transistor related defects or resistive interconnect defects. The new delay defect/failure characterization method is based on low voltage test and delay defect detection in slack interval (DDSI) method. Experimental results were presented to validate the effectiveness of the new method. Practical considerations were also addressed for adoption of the methodology.
22160794
Output hazard-free transition tests for silicon calibrated scan based delay testing
Architectural restrictions of scan greatly limit the effectiveness of traditional scan based delay tests. It has been recently shown that additional testing for delays on short paths using fast clocks can significantly lower DPM. However, accurately obtaining the needed timing information for such tests from simulation is extremely difficult. The simulations must not only accurately account for the effects of process parameter variations, but also power supply noise and crosstalk from the excessive switching activity of scan tests. We suggest that learning signal timing information on silicon to "calibrate" such tests can be much more accurate and cost effective. However, such an approach requires that the outputs of the applied tests be hazard free to avoid learning incorrect timing due to a glitch at the output. Simulation results presented here indicate that such output hazard free test can be obtained with an average coverage only about 10% below the transition delay fault coverage for both launch-on-shift (LOS) and launch-on-capture (LOG) modes
18125681
A Speaker Tracking Algorithm Based on Audio and Visual Information Fusion Using Particle Filter
Object tracking by sensor fusion has become an active research area in recent years, but how to fuse various information in an efficient and robust way is still an open problem. This paper presents a new algorithm for tracking speaker based on audio and visual information fusion using particle filter. A closed-loop architecture with reliability of each individual tracker is adopted, and a new method for data fusion and reliability adjustment is proposed. Experiments show the new algorithm is efficient in fusing information and robust to noise.