A randomized approximation algorithm for computing bucket orders

We show that a simple randomized algorithm has an expected constant factor approximation guarantee for fitting bucket orders to a set of pairwise preferences.     

Improved deterministic approximation algorithms for Max TSP

We present an O(n³)-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically , where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n³)-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically . Both algorithms improve on the previous bests.     

An approximation algorithm for interval data minmax regret combinatorial optimization problems

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval data is considered. In many cases, the minmax regret versions of the classical, polynomially solvable, combinatorial optimization problems become NP-hard and no approximation algorithms for them have been known. Our main result is a polynomial time approximation algorithm with a performance ratio of 2 for this class of problems.     

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.     

A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem

Motivated by the problem of supporting energy-efficient broadcasting in ad hoc wireless networks, we study the Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. We present the first logarithmic approximation algorithm for the problem which uses an interesting reduction to Node-Weighted Connected Dominating Set.     

An approximation algorithm for sequential rectangle placement

We present a constant factor, polynomial time approximation algorithm for the problem of scheduling a sequence of rectangles on a matrix. The approximation is on the area covered by the rectangles, and a rectangle is placed on the matrix only if all its preceding rectangles in the sequence were already placed.     

Efficient Randomized Algorithms for the Repeated Median Line Estimator

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Recently there has been a great deal of interest is robust estimators, because of their lack of sensitivity to outlying data points. The basic measure of the robustness of an estimator is its breakdown point, that is, the fraction (up to 50%) of outlying data points that can corrupt the estimator. One problem with robust estimators is that achieving high breakdown points (near 50%) has proved to be computationally demanding. In this paper we present the best known theoretical algorithm and a practical subquadratic algorithm for computing a 50% breakdown point line estimator, the Siegel or repeated median line estimator. We first present an O(n\log n) randomized expected-time algorithm, where n is the number of given points. This algorithm relies, however, on sophisticated data structures. We also present a very simple O(n log ² n) randomized algorithm for this problem, which uses no complex data structures. We provide empirical evidence that, for many realistic input distributions, the running time of this second algorithm is actually O(n log n) expected time. Received January 25, 1995; revised May 17, 1996. Communciated by L. J. Guibas.     

A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

Improved approximation algorithms for MAXk-CUT and MAX BISECTION

Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph intok blocks so as to maximize the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite programming relaxation. The first author was supported in part by NSF Grant CCR-9225008. The work described here was undertaken while the second author was visiting Carnegie Mellon University; at that time he was a Nuffield Science Research Fellow, and was supported in part by Grant GR/F 90363 of the UK Science and Engineering Research Council, and Esprit Working Group 7097 “RAND”.     

A fast deterministic smallest enclosing disk approximation algorithm

We describe a simple and fast -time algorithm for finding a (1+?)-approximation of the smallest enclosing disk of a planar set of n points or disks. Experimental results of a readily available implementation are presented.     

An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes

The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c₁,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c₁,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large.     

An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G=(V,E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a -approximation algorithm, where c is an arbitrary constant.In this paper, we present a -approximation algorithm based on an LP relaxation, where χ^′(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of |V|. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also -approximable. From edge-coloring theory, the approximation ratio of our algorithm is , where Δ(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least . Moreover, χ^′(G) is Δ(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible.     

A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2ⁿ) (resp. O(3ⁿ)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms.     

A note on the greedy algorithm for the unsplittable flow problem

In a recent paper Chekuri and Khanna improved the analysis of the greedy algorithm for the edge disjoint paths problem and proved the same bounds also for the related uniform capacity unsplittable flow problem. Here we show that their ideas can be used to get the same approximation ratio even for the more general Unsplittable Flow Problem with nonuniform edge capacities.     

Outliers, inliers and the generalized least trinuned squares estimator in system identification

The least trimmed squares estimator (LTS) is a well known robust estimator in terms of protecting the estimate from the outliers. Its high computational complexity is however a problem in practice. We show that the LTS estimate can be obtained by a simple algorithm with the complexity O( N In N) for large N, where N is the number of measurements. We also show that though the LTS is robust in terms of the outliers, it is sensitive to the inliers. The concept of the inliers is introduced. Moreover, the Generalized Least Trimmed Squares estimator (GLTS) together with its solution are presented that reduces the effect of both the outliers and the inliers.     

Outliers, inliers and the generalized least trimmed squares estimator in system identification

The least trimmed squares estimator (LTS) is a well known robust estinaator in terms of protecting the estimatefrom the outliers. Its high computational complexity is however a problem in practice. We show that the LTS estimate can be obtained by a simple algorithm with the complexity O( N In N) for large N, where N is the number of measurements. We also showthat though the LTS is robust in terms of the outliers, it is sensitive to the inliers. The concept of the inliers is introduced. Moreover, the Generalized Least Trimmed Squares estimator (GLTS) together with its solution are presented that reduces the effect of both the outliers and the inliers.     

A note on improving the performance of approximation algorithms for radiation therapy

The segment minimization problem consists of representing an integer matrix as the sum of the fewest number of integer matrices each of which have the property that the non-zeroes in each row are consecutive. This has direct applications to an effective form of cancer treatment. Using several insights, we extend previous results to obtain constant-factor improvements in the approximation guarantees. We show that these improvements yield better performance by providing an experimental evaluation of all known approximation algorithms using both synthetic and real-world clinical data. Our algorithms are superior for 76% of instances and we argue for their utility alongside the heuristic approaches used in practice.     

A note on the approximation of mean-payoff games

We consider the problem of designing approximation schemes for the values of mean-payoff games. It was recently shown that (1) mean-payoff with rational weights scaled on [−1,1]$[-1,1]$ admit additive fully-polynomial approximation schemes, and (2) mean-payoff games with positive weights admit relative fully-polynomial approximation schemes. We show that the problem of designing additive/relative approximation schemes for general mean-payoff games (i.e. with no constraint on their edge-weights) is P-time equivalent to determining their exact solution.     

An ellipsoid algorithm for probabilistic robust controller design

In this paper, a new iterative approach to probabilistic robust controller design is presented, which is applicable to any robust controller/filter design problem that can be represented as an LMI feasibility problem. Recently, a probabilistic Subgradient Iteration algorithm was proposed for solving LMIs. It transforms the initial feasibility problem to an equivalent convex optimization problem, which is subsequently solved by means of an iterative algorithm. While this algorithm always converges to a feasible solution in a finite number of iterations, it requires that the radius of a non-empty ball contained into the solution set is known a priori. This rather restrictive assumption is released in this paper, while retaining the convergence property. Given an initial ellipsoid that contains the solution set, the approach proposed here iteratively generates a sequence of ellipsoids with decreasing volumes, all containing the solution set. At each iteration a random uncertainty sample is generated with a specified probability density, which parameterizes an LMI. For this LMI the next minimum-volume ellipsoid that contains the solution set is computed. An upper bound on the maximum number of possible correction steps, that can be performed by the algorithm before finding a feasible solution, is derived. A method for finding an initial ellipsoid containing the solution set, which is necessary for initialization of the optimization, is also given. The proposed approach is illustrated on a real-life diesel actuator benchmark model with real parametric uncertainty, for which a robust state-feedback controller is designed.