THE ANALYSIS OF OUTLYING DATA POINTS USING ROBUST REGRESSION: A MULTIVARIATE PROBLEM-BANK IDENTIFICATION MODEL*

Because the eight largest bank failures in United States history have occurred since 1973 [24], the development of early-warning problem-bank identification models is an important undertaking. It has been shown previously [3] [5] that M-estimator robust regression provides such a model. The present paper develops a similar model for the multivariate case using both a robustified Mahalanobis distance analysis [21] and principal components analysis [10]. In addition to providing a successful presumptive problem-bank identification model, combining the use of the M-estimator robust regression procedure and the robust Mahalanobis distance procedure with principal components analysis is also demonstrated to be a general method of outlier detection. The results from using these procedures are compared to some previously suggested procedures, and general conclusions are drawn.     

Concepts,Theory, and Techniques ROBUST METHODS: AN ALTERNATIVE APPROACH FOR ANALYZING DATA SETS CONTAINING INFLUENTIAL DATA POINTS

Recent advances in statistical estimation theory have resulted in the development of new procedures, called robust methods, that can be used to estimate the coefficients of a regression model. Because such methods take into account the impact of discrepant data points during the initial estimation process, they offer a number of advantages over ordinary least squares and other analytical procedures (such as the analysis of outliers or regression diagnostics). This paper describes the robust method of analysis and illustrates its potential usefulness by applying the technique to two data sets. The first application uses artificial data; the second uses a data set analyzed previously by Tufte [15] and, more recently, by Chatterjee and Wiseman [6].     

Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n ^o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of \fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs.     

Node-weighted Steiner tree approximation in unit disk graphs

Given a graph G=(V,E) with node weight w:V→R ⁺ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n ^O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs. As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs.     

The Polymatroid Steiner Problems

The Steiner tree problem asks for a minimum cost tree spanning a given set of terminals S⊂eqV in a weighted graph G = (V,E,c), c:E→ R⁺. In this paper we consider a generalization of the Steiner tree problem, so called Polymatroid Steiner Problem, in which a polymatroid P = P(V) is defined on V and the Steiner tree is required to span at least one base of P (in particular, there may be a single base S⊂eqV). This formulation is motivated by the following application in sensor networks – given a set of sensors S = {s₁,…,s_k}, each sensor s_i can choose to monitor only a single target from a subset of targets X_i, find minimum cost tree spanning a set of sensors capable of monitoring the set of all targets X = X₁ ∪ … ∪ X_k. The Polymatroid Steiner Problem generalizes many known Steiner tree problem formulations including the group and covering Steiner tree problems. We show that this problem can be solved with the polylogarithmic approximation ratio by a generalization of the combinatorial algorithm of Chekuri et al. (2002).We also define the Polymatroid directed Steiner problem which asks for a minimum cost arborescence connecting a given root to a base of a polymatroid P defined on the terminal set S. We show that this problem can be approximately solved by algorithms generalizing methods of Chekuri et al. (2002).A preliminary version of this paper appeared in ISAAC 2004     

Polynomial time approximation schemes for minimum disk cover problems

The following planar minimum disk cover problem is considered in this paper: given a set D\mathcal{D} of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within a factor of (1+ε) in O(mn^{O(\frac1e2log2\frac1e)})\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})}) time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem are considered and approximation schemes are designed.     

Parameterized lower bound and inapproximability of polylogarithmic string barcoding

String barcoding is a method that can identify microorganisms by analyzing their genome sequences. In this paper, we study the polylogarithmic string barcoding problem, where the lengths of the substrings in the testing set are polylogarithmically bounded. In particular, we show that the polylogarithmic string barcoding problem remains NP-hard and moreover, for a problem instance with n sequences, it is NP-hard to achieve an approximate ratio within dln n in polynomial time, where d is some constant. We then consider the parameterized polylogarithmic string barcoding problem, where the number of substrings in the test set is considered to be a fixed parameter k. We show that, unless W[2]=FPT, there does not exist a 2 ^O(k) n ^c algorithm that can decide whether a test set of size k exists or not, where c is a constant independent of n and k.     

Point sets in the unit square and large areas of convex hulls of subsets of points

In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]² are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n ^6k−4) time algorithm is given, which finds distributions of n points in [0,1]² such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)^1/(j−2)/n ^{(j−1)/(j−2)}).     

Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem

In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function 〈x, Ax〉 + 〈c, x〉 over the set {0,1} ⁿ where c is a vector in ℝ ⁿ and A is a symmetric real n × n matrix of constant rank r. We first present a pseudo-polynomial algorithm for solving the problem CR-QP01, which is known to be NP-hard already for r = 1. We then derive two new classes of special cases of the CR-QP01 which can be solved in polynomial time. These classes result from further restrictions on the matrix A. Finally we compare our algorithm with the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite A and extend the range of applicability of the latter algorithm. It turns out that neither of the two algorithms dominates the other with respect to the class of instances which can be solved in polynomial time.     

An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n ³) time per motif with O(n) space, in particular O(n ³) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms. This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France.     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

Selective support vector machines

In this study we introduce a generalized support vector classification problem: Let X _i , i=1,…,n be mutually exclusive sets of pattern vectors such that all pattern vectors x _i,k , k=1,…,|X _i | have the same class label y _i . Select only one pattern vector $x_{i,k^{*}}In this study we introduce a generalized support vector classification problem: Let X _i , i=1,…,n be mutually exclusive sets of pattern vectors such that all pattern vectors x _i,k , k=1,…,|X _i | have the same class label y _i . Select only one pattern vector from each set X _i such that the margin between the set of selected positive and negative pattern vectors are maximized. This problem is formulated as a quadratic mixed 0-1 programming problem, which is a generalization of the standard support vector classifiers. The quadratic mixed 0-1 formulation is shown to be -hard. An alternative approach is proposed with the free slack concept. Primal and dual formulations are introduced for linear and nonlinear classification. These formulations provide flexibility to the separating hyperplane to identify the pattern vectors with large margin. Iterative elimination and direct selection methods are developed to select such pattern vectors using the alternative formulations. These methods are compared with a na?ve method on simulated data. The iterative elimination method is also applied to neural data from a visuomotor categorical discrimination task to classify highly cognitive brain activities.     

Domination in graphs with bounded propagation: algorithms,formulations and hardness results

We introduce a hierarchy of problems between the Dominating Set problem and the Power Dominating Set (PDS) problem called the ℓ-round power dominating set (ℓ-round PDS, for short) problem. For ℓ=1, this is the Dominating Set problem, and for ℓ≥n−1, this is the PDS problem; here n denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or it has a neighbor in S, or (2) v has a neighbor u such that u and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the Dominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The ℓ-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most ℓ−1 rounds. We prove that ℓ-round PDS cannot be approximated better than 2^log1-en2^{\log^{1-\epsilon}{n}} even for ℓ=4 in general graphs. We provide a dynamic programming algorithm to solve ℓ-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation scheme) for ℓ-round PDS on planar graphs for l = O(\fraclognloglogn)\ell=O(\frac{\log{n}}{\log{\log{n}}}) . Finally, we give integer programming formulations for ℓ-round PDS.     

A PTAS for Semiconductor Burn-in Scheduling

In this paper a polynomial time approximation scheme, PTAS for short, is presented for the problem of scheduling jobs in a batch processing system. Each job has a pre-defined release date, which indicates when the job is available, and a pre-defined burn-in time, which is the least time needed for processing the job. At one time, at most B jobs can be processed together, where B is a pre-given number. No preemption is permitted.Research supported in part by an RGC CERG grant [CityU 1081/02E] and a grant from CityU [7001347].Supported by the fund from NSFC under grant numbers 10271065 and 60373025.     

The orbit problem is in the GapL hierarchy

The Orbit problem is defined as follows: Given a matrix A∈ℚ ^n×n and vectors x,y∈ℚ ⁿ , does there exist a non-negative integer i such that A ⁱ x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808–821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for C₌L with respect to logspace many-one reductions.     

A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways

The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a -approximation to the optimal cost in O(n ^O(c)log(n) time.     

On Some Polyhedra Covering Problems

Let P ⁰, P ¹ be two simple polyhedra and let P ² be a convex polyhedron in E ³. Polyhedron P ⁰ is said to be covered by polyhedra P ¹ and P ² if every point of P ⁰ is a point of P ¹ P ². The following polyhedron covering problem is studied: given the positions of P ⁰, P ¹, and P ² in the xy-coordinate system, determine whether or not P ⁰ can be covered by P ¹ P ² via translation and rotation of P ¹ and P ²; furthermore, find the exact covering positions of these polyhedra if such a cover exists. It is shown in this paper that if only translation is allowed, then the covering problem of P ⁰, P ¹ and P ² can be solved in O(m ² n ²(m + n)l)) polynomial time, where m, n, and l are the sizes of P ⁰, P ¹, and P ², respectively. The method can be easily extended to the problem in E ^d for any fixed d > 3.     

Minimizing the maximum bump cost in linear extensions of a poset

A linear extension of a poset P=(X,?) is a permutation x ₁,x ₂,…,x _|X| of X such that i<j whenever x _i ?x _j . For a given poset P=(X,?) and a cost function c(x,y) defined on X×X, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.     

On the inapproximability of the exemplar conserved interval distance problem of genomes

In this paper we present two main results about the inapproximability of the exemplar conserved interval distance problem of genomes. First, we prove that it is NP-complete to decide whether the exemplar conserved interval distance between any two genomes is zero or not. This result implies that the exemplar conserved interval distance problem does not admit any approximation in polynomial time, unless P=NP. In fact, this result holds, even when every gene appears in each of the given genomes at most three times. Second, we strengthen the first result under a weaker definition of approximation, called weak approximation. We show that the exemplar conserved interval distance problem does not admit any weak approximation within a super-linear factor of , where m is the maximal length of the given genomes. We also investigate polynomial time algorithms for solving the exemplar conserved interval distance problem when certain constrains are given. We prove that the zero exemplar conserved interval distance problem of two genomes is decidable in polynomial time when one genome is O(log n)-spanned. We also prove that one can solve the constant-sized exemplar conserved interval distance problem in polynomial time, provided that one genome is trivial.     

Constructing the Maximum Consensus Tree from Rooted Triples

We investigated the problem of constructing the maximum consensus tree from rooted triples. We showed the NP-hardness of the problem and developed exact and heuristic algorithms. The exact algorithm is based on the dynamic programming strategy and runs in O((m + n ²)3 ⁿ ) time and O(2 ⁿ ) space. The heuristic algorithms run in polynomial time and their performances are tested and shown by comparing with the optimal solutions. In the tests, the worst and average relative error ratios are 1.200 and 1.072 respectively. We also implemented the two heuristic algorithms proposed by Gasieniec et al. The experimental result shows that our heuristic algorithm is better than theirs in most of the tests.