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.     

On the equitable k *-laceability of hypercubes

Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C _k (u,v). A k-container is a k ^*-container if it spans all vertices of G. We define G to be a k ^*-laceable graph if there is a k ^*-container joining any two vertices from different partite sets. A k ^*-container C _k ^*(u,v)={P ₁,…,P _k } is equitable if ||V(P _i )|−|V(P _j )||≤2 for all 1≤i,j≤k. A graph is equitably k ^*-laceable if there is an equitable k ^*-container joining any two vertices in different partite sets. Let Q _n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q _n is equitably k ^*-laceable for all k≤n−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.     

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     

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.     

Maximizing Profits of Routing in WDM Networks

Let G = (V, E) be a ring (or chain) network representing an optical wavelength division multiplexing (WDM) network with k channels, where each edge e_j has an integer capacity c_j. A request s_i,t_i is a pair of two nodes in G. Given m requests s_i,t_i, i = 1, 2, ..., m, each with a profit value p_i, we would like to design/route a k-colorable set of paths for some (may not be all) of the m requests such that each edge e_j in G is used at most c_j times and the total profit of the set of designed paths is maximized. Here two paths cannot have the same color (channel) if they share some common edge(s).This problem arises in optical communication networks. In this paper, we present a polynomial-time algorithm to solve the problem when G is a chain. When G is a ring, however, the optimization problem is NP-hard (Wan and Liu, 1998), we present a 2-approximation algorithm based on our solution to the chain network. Similarly, some results in a bidirected chain and a bidirected ring are obtained.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.     

Partitioning a weighted partial order

The problem of partitioning a partially ordered set into a minimum number of chains is a well-known problem. In this paper we study a generalization of this problem, where we not only assume that the chains have bounded size, but also that a weight w _i is given for each element i in the partial order such that w _i ≤w _j if i ≺ j. The problem is then to partition the partial order into a minimum-weight set of chains of bounded size, where the weight of a chain equals the weight of the heaviest element in the chain. We prove that this problem is -hard, and we propose and analyze lower bounds for this problem. Based on these lower bounds, we exhibit a 2-approximation algorithm, and show that it is tight. We report computational results for a number of real-world and randomly generated problem instances.     

Testing Hypotheses About the Number of Factors in Large Factor Models

In this paper we study high‐dimensional time series that have the generalized dynamic factor structure. We develop a test of the null of k₀ factors against the alternative that the number of factors is larger than k₀ but no larger than k₁>k₀. Our test statistic equals max_{k0<k k1}(γ_k−γ_k+1)(γ_k+1−γ_k+2), where γ_i is the ith largest eigenvalue of the smoothed periodogram estimate of the spectral density matrix of data at a prespecified frequency. We describe the asymptotic distribution of the statistic, as the dimensionality and the number of observations rise, as a function of the Tracy–Widom distribution and tabulate the critical values of the test. As an application, we test different hypotheses about the number of dynamic factors in macroeconomic time series and about the number of dynamic factors driving excess stock returns.     

Note on the hardness of generalized connectivity

Let G be a nontrivial connected graph of order n and let k be an integer with 2??k??n. For a set S of k vertices of G, let ??(S) denote the maximum number ? of edge-disjoint trees T ₁,T ₂,??,T _? in G such that V(T _i )??V(T _j )=S for every pair i,j of distinct integers with 1??i,j???. Chartrand et al. generalized the concept of connectivity as follows: The k-connectivity, denoted by ?? _k (G), of G is defined by ?? _k (G)=min{??(S)}, where the minimum is taken over all k-subsets S of V(G). Thus ?? ₂(G)=??(G), where ??(G) is the connectivity of G, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of determining the generalized connectivity of a graph. At first, we obtain that for two fixed positive integers k ₁ and k ₂, given a graph G and a k ₁-subset S of V(G), the problem of deciding whether G contains k ₂ internally disjoint trees connecting S can be solved by a polynomial-time algorithm. Then, we show that when k ₁ is a fixed integer of at least 4, but k ₂ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when k ₂ is a fixed integer of at least 2, but k ₁ is not a fixed integer, we show that the problem also becomes NP-complete.     

The total {k}-domatic number of a graph

For a positive integer k, a total {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0,1,2,…,k} such that for any vertex v∈V(G), the condition ∑ _u∈N(v) f(u)≥k is fulfilled, where N(v) is the open neighborhood of v. A set {f ₁,f ₂,…,f _d } of total {k}-dominating functions on G with the property that ?_i=1^df_i(v) ￡ k\sum_{i=1}^{d}f_{i}(v)\le k for each v∈V(G), is called a total {k}-dominating family (of functions) on G. The maximum number of functions in a total {k}-dominating family on G is the total {k}-domatic number of G, denoted by d_t^{k}(G)d_{t}^{\{k\}}(G). Note that d_t^{1}(G)d_{t}^{\{1\}}(G) is the classic total domatic number d _t (G). In this paper we initiate the study of the total {k}-domatic number in graphs and we present some bounds for d_t^{k}(G)d_{t}^{\{k\}}(G). Many of the known bounds of d _t (G) are immediate consequences of our results.     

A hybrid beam search looking-ahead algorithm for the circular packing problem

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r _i and its demand b _i . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.     

Strongly chordal and chordal bipartite graphs are sandwich monotone

A graph class is sandwich monotone if, for every pair of its graphs G ₁=(V,E ₁) and G ₂=(V,E ₂) with E ₁⊂E ₂, there is an ordering e ₁,…,e _k of the edges in E ₂∖E ₁ such that G=(V,E ₁∪{e ₁,…,e _i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.     

The subdivision-constrained routing requests problem

We are given a digraph D=(V,A;w), a length (delay) function w:A→R ⁺, a positive integer d and a set $\mathcal{P}=\{(s_{i},t_{i};B_{i}) | i=1,2,\ldots,k\}$ of k requests, where s _i ∈V is called as the ith source node, t _i ∈V is called the ith sink node and B _i is called as the ith length constraint. For a given positive integer d, the subdivision-constrained routing requests problem (SCRR, for short) is to find a directed subgraph D′=(V′,A′) of D, satisfying the two constraints: (1) Each request (s _i ,t _i ;B _i ) has a path P _i from s _i to t _i in D′ with length $w(P_{i})=\sum_{e\in P_{i}} w(e)$ no more than B _i ; (2) Insert some nodes uniformly on each arc e∈A′ to ensure that each new arc has length no more than d. The objective is to minimize the total number of the nodes inserted on the arcs in A′. We obtain the following three main results: (1) The SCRR problem is at least as hard as the set cover problem even if each request has the same source s, i.e., s _i =s for each i=1,2,…,k; (2) For each request (s,t;B), we design a dynamic programming algorithm to find a path from s to t with length no more than B such that the number of the nodes inserted on such a path is minimized, and as a corollary, we present a k-approximation algorithm to solve the SCRR problem for any k requests; (3) We finally present an optimal algorithm for the case where $\mathcal{P}$ contains all possible requests (s _i ,t _i ) in V×V and B _i is equal to the length of the shortest path in D from s _i to t _i . To the best of our knowledge, this is the first time that the dynamic programming algorithm within polynomial time in (2) is designed for a weighted optimization problem while previous optimal algorithms run in pseudo-polynomial time.     

Analysis of Exogenous Components of Mortality Risks

A new technique for deriving exogenous components of mortality risks from national vital statistics has been developed. Each observed death rate D_ij (where i corresponds to calendar time (year or interval of years) and j denotes the number of corresponding age group) was represented as D_ij=A_j+B_iC_j, and unknown quantities A_j, B_i, and C_j were estimated by a special procedure using the least-squares principle. The coefficients of variation do not exceed 10%. It is shown that the term A_j can be interpreted as the endogenous and the second term B_iC_j as the exogenous components of the death rate. The aggregate of endogenous components A_j can be described by a regression function, corresponding to the Gompertz-Makeham law, A(τ) =γ+β· eατ, where γ, β, and α are constants, τ is age, AττAττA_j, and τ_j, is the value of age τ in jth age group. The coefficients of variation for such a representation does not exceed 4%. An analysis of exogenous risk levels in the Moscow and Russian populations during 1980–1995 shows that since 1992 all components of exogenous risk in the Moscow population had been increasing up to 1994. The greatest contribution to the total level of exogenous risk was lethal diseases, and their death rate was 387 deaths per 100,000 persons in 1994, i.e., 61.9% of all deaths. The dynamics of exogenous mortality risk change during 1990–1994 in the Moscow population and in the Russian population without Moscow had been identical: the risk had been increasing, and its value in the Russian population had been higher than that in the Moscow population.     

The Independence Number of Graphs with a Forbidden Cycle and Ramsey Numbers

Let k 5 be a fixed integer and let m = (k – 1)/2. It is shown that the independence number of a C _k-free graph is at least c ₁[ d(v)^{1/(m – 1)}]^{(m – 1)/m} and that, for odd k, the Ramsey number r(C _k, K _n) is at most c ₂(n ^{m + 1}/log n)^1/m , where c ₁ = c ₁(m) > 0 and c ₂ = c ₂(m) > 0.     

Improving an upper bound on the size of k-regular induced subgraphs

This paper considers the NP-hard graph problem of determining a maximum cardinality subset of vertices inducing a k-regular subgraph. For any graph G, this maximum will be denoted by α _k (G). From a well known Motzkin-Straus result, a relationship is deduced between α _k (G) and the independence number α(G). Next, it is proved that the upper bounds υ _k (G) introduced in Cardoso et al. (J. Comb. Optim., 14, 455–463, 2007) can easily be computed from υ ₀(G), for any positive integer k. This relationship also allows one to present an alternative proof of the Hoffman bound extension introduced in the above paper. The paper continues with the introduction of a new upper bound on α _k (G) improving υ _k (G). Due to the difficulty of computing this improved bound, two methods are provided for approximating it. Finally, some computational experiments which were performed to compare all bounds studied are reported.     

Packing <Emphasis Type="Bold">[1, Δ]</Emphasis>-factors in graphs of small degree

Given an undirected, connected graph G with maximum degree Δ, we introduce the concept of a [1, Δ]-factor k-packing in G, defined as a set of k edge-disjoint subgraphs of G such that every vertex of G has an incident edge in at least one subgraph. The problem of deciding whether a graph admits a [1,Δ]-factor k-packing is shown to be solvable in linear time for k = 2, but NP-complete for all k≥ 3. For k = 2, the optimisation problem of minimising the total number of edges of the subgraphs of the packing is NP-hard even when restricted to subcubic planar graphs, but can in general be approximated within a factor of by reduction to the Maximum 2-Edge-Colorable Subgraph problem. Finally, we discuss implications of the obtained results for the problem of fault-tolerant guarding of a grid, which provides the main motivation for research.     

Semi-online scheduling on 2 machines under a grade of service provision with bounded processing times

We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p _i of every job J _i is bounded by an interval [a,α a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs’ processing times, we denote it by semi-online problem. We deal with two semi-online problems.     

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.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.