One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions

Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned n_i numbers with n_i lying in a given range. The goal is to maximize a Schur convex function F whose ith argument is the sum of numbers assigned to part i. The shape of a partition is the vector consisting of the sizes of its parts, further, a shape (without referring to a particular partition) is a vector of nonnegative integers (n₁,..., n_p) which sum to n. A partition is called size-consecutive if there is a ranking of the parts which is consistent with their sizes, and all elements in a higher-ranked part exceed all elements in the lower-ranked part. We demonstrate that one can restrict attention to size-consecutive partitions with shapes that are nonmajorized, we study these shapes, bound their numbers and develop algorithms to enumerate them. Our study extends the analysis of a previous paper by Hwang and Rothblum which discussed the above problem assuming the existence of a majorizing shape. This research is partially supported by ROC National Science grant NSC 92-2115-M-009-014.     

A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J _j , its processing time and delivery time are denoted by p _j and q _j , respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J _j , q _j ≤p _j ; (2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J _i and J _j , p _i >p _j implies q _i ≥q _j . We provide an on-line algorithm with competitive ratio for both problems, and the results are the best possible. Project supported by NSFC (10671183).     

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.     

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.     

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.     

New algorithms for k-center and extensions

The problem of interest is covering a given point set with homothetic copies of several convex containers C ₁,…,C _k , while the objective is to minimize the maximum over the dilatation factors. Such k-containment problems arise in various applications, e.g. in facility location, shape fitting, data classification or clustering. So far most attention has been paid to the special case of the Euclidean k-center problem, where all containers C _i are Euclidean unit balls. Recent developments based on so-called core-sets enable not only better theoretical bounds in the running time of approximation algorithms but also improvements in practically solvable input sizes. Here, we present some new geometric inequalities and a Mixed-Integer-Convex-Programming formulation. Both are used in a very effective branch-and-bound routine which not only improves on best known running times in the Euclidean case but also handles general and even different containers among the C _i .     

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.     

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.     

The Expected Number of Nash Equilibria of a Normal Form Game

Fix finite pure strategy sets _S1,…,_Sn , and let S=_S1×⋯×_Sn . In our model of a random game the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere in ℝ^S. For given nonempty _T1⊂_S1,…,_Tn⊂_Sn we give a computationally implementable formula for the mean number of Nash equilibria in which each agent i's mixed strategy has support T_i. The formula is the product of two expressions. The first is the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the sets T_i. The second may be construed as the “probability” that such an equilibrium remains an equilibrium when the strategies in the sets _Si∖_Ti become available.     

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.     

A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients) D í V\mathcal{D}\subseteq V , and a parameter M≥1. Each facility i has a nonnegative opening cost f _i and each client j has d _j units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is ?_{i ? F}f_i+?_{j ? D}d_jc_i(j)j+M?_{e ? T}c_e\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e} , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).     

Edge-colouring of joins of regular graphs, I

We prove that the edges of every even graph G=G ₁+G ₂ that is the join of two regular graphs G _i =(V _i ,E _i ) can be coloured with Δ(G) colours, whenever Δ(G)=Δ(G ₂)+|V ₁|. The proof of this result yields a combinatorial algorithm to optimally colour the edges of this type of graphs.     

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.     

Perceptions and Expected Immediate Reactions to Severe Storm Displays

The National Weather Service has adopted warning polygons that more specifically indicate the risk area than its previous county‐wide warnings. However, these polygons are not defined in terms of numerical strike probabilities (p_s). To better understand people's interpretations of warning polygons, 167 participants were shown 23 hypothetical scenarios in one of three information conditions—polygon‐only (Condition A), polygon + tornadic storm cell (Condition B), and polygon + tornadic storm cell + flanking nontornadic storm cells (Condition C). Participants judged each polygon's p_s and reported the likelihood of taking nine different response actions. The polygon‐only condition replicated the results of previous studies; p_s was highest at the polygon's centroid and declined in all directions from there. The two conditions displaying storm cells differed from the polygon‐only condition only in having p_s just as high at the polygon's edge nearest the storm cell as at its centroid. Overall, p_s values were positively correlated with expectations of continuing normal activities, seeking information from social sources, seeking shelter, and evacuating by car. These results indicate that participants make more appropriate p_s judgments when polygons are presented in their natural context of radar displays than when they are presented in isolation. However, the fact that p_s judgments had moderately positive correlations with both sheltering (a generally appropriate response) and evacuation (a generally inappropriate response) suggests that experiment participants experience the same ambivalence about these two protective actions as people threatened by actual tornadoes.     

An Econometric Model of Network Formation With Degree Heterogeneity

I introduce a model of undirected dyadic link formation which allows for assortative matching on observed agent characteristics (homophily) as well as unrestricted agent‐level heterogeneity in link surplus (degree heterogeneity). Like in fixed effects panel data analyses, the joint distribution of observed and unobserved agent‐level characteristics is left unrestricted. Two estimators for the (common) homophily parameter, β₀, are developed and their properties studied under an asymptotic sequence involving a single network growing large. The first, tetrad logit (TL), estimator conditions on a sufficient statistic for the degree heterogeneity. The second, joint maximum likelihood (JML), estimator treats the degree heterogeneity {A_i0}_{i = 1}^N as additional (incidental) parameters to be estimated. The TL estimate is consistent under both sparse and dense graph sequences, whereas consistency of the JML estimate is shown only under dense graph sequences.     

On the Existence of Pure and Mixed Strategy Nash Equilibria in Discontinuous Games

A game is better-reply secure if for every nonequilibrium strategy x^* and every payoff vector limit u^* resulting from strategies approaching x^*, some player i has a strategy yielding a payoff strictly above u_i^* even if the others deviate slightly from x^*. If strategy spaces are compact and convex, payoffs are quasiconcave in the owner's strategy, and the game is better-reply secure, then a pure strategy Nash equilibrium exists. Better-reply security holds in many economic games. It also permits new results on the existence of symmetric and mixed strategy Nash equilibria.     

Dermal Uptake of 18 Dilute Aqueous Chemicals: In Vivo Disappearance‐Method Measures Greatly Exceed In Vitro‐Based Predictions

Average rates of total dermal uptake (K_up) from short‐term (e.g., bathing) contact with dilute aqueous organic chemicals (DAOCs) are typically estimated from steady‐state in vitro diffusion‐cell measures of chemical permeability (K_p) through skin into receptor solution. Widely used (“PCR‐vitro”) methods estimate K_up by applying diffusion theory to increase K_p predictions made by a physico‐chemical regression (PCR) model that was fit to a large set of K_p measures. Here, K_up predictions for 18 DAOCs made by three PCR‐vitro models (EPA, NIOSH, and MH) were compared to previous in vivo measures obtained by methods unlikely to underestimate K_up. A new PCR model fit to all 18 measures is accurate to within approximately threefold (r = 0.91, p < 10^?5), but the PCR‐vitro predictions (r > 0.63) all tend to underestimate the K_up measures by mean factors (UF, and p value for testing UF = 1) of 10 (EPA, p < 10^?6), 11 (NIOSH, p < 10^?8), and 6.2 (MH, p = 0.018). For all three PCR‐vitro models, log(UF) correlates negatively with molecular weight (r² = 0.31 to 0.84, p = 0.017 to < 10^?6) but not with log(vapor pressure) as an additional predictor (p > 0.05), so vapor pressure appears not to explain the significant in vivo/PCR‐vitro discrepancy. Until this discrepancy is explained, careful in vivo measures of K_up should be obtained for more chemicals, the expanded in vivo database should be compared to in vitro‐based predictions, and in vivo data should be considered in assessing aqueous dermal exposure and its uncertainty.     

On cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

Will More Purchasing Options Benefit Customers?

This paper considers the sale of a seasonal product in the face of strategic customers. At the beginning of the selling season, the retailer announces both the price p_h at which the product will be sold during the selling season and the post‐season clearance price p<p_h for unsold items. We analyze two operating regimes: The “no reservation regime” allows a buyer either to purchase the product at price p_h when he arrives or to enter a lottery to purchase at price p if the product remains unsold. The “reservation regime” offers each buyer one extra option than the no reservation regime: reserve the product for purchase at the clearance price p. If the buyer reserves the product under the reservation regime and if it remains unsold at the end of the selling season, then he is obligated to purchase it at price p. We consider a situation in which heterogeneous customers with probabilistic valuation arrive in accord with a Poisson process. We characterize the rational purchasing behavior wherein each arriving customer is strategic; each customer takes other customers' purchasing behavior into consideration. By considering the Nash equilibrium of this game, we show that strategic customer behavior can render the customer to be worse off and the retailer to be better off under the reservation regime, despite the fact that this regime offers one extra option (reservation) to a customer. Hence, more purchasing options do not necessarily benefit customers.     

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.