A local search approximation algorithm for a squared metric <Emphasis Type="Italic">k</Emphasis>-facility location problem

We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have deadlines and machine-type dependent sizes. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. As we observe the slack of jobs to have a fundamental influence on the competitiveness, we parameterize instances by their (minimum) slack. An instance is called to have a slack of \(\beta \) if, for all jobs, the difference between the job’s release time and the latest point in time at which it needs to be started is at least \(\beta \). While for \(\beta < s\) no finite competitiveness is possible, our main result is an online algorithm for \(\beta = (1+\varepsilon )s\) with Open image in new window , where s denotes the largest setup time. Its competitiveness only depends on \(\varepsilon \) and the cost ratio of the machine types and is proven to be optimal up to a factor of Open image in new window .     

$$(\alpha , \tau )$$-Monitoring for event detection in wireless sensor networks

Detecting abnormal events is one of the fundamental issues in wireless sensor networks (WSNs). In this paper, we investigate \((\alpha ,\tau )\)-monitoring in WSNs. For a given monitored threshold \(\alpha \), we prove that (i) the tight upper bound of \(\Pr [{S(t)} \ge \alpha ]\) is \(O\left( {\exp \left\{ { - n\ell \left( {\frac{\alpha }{{nsup}},\frac{{\mu (t)}}{{nsup}}} \right) } \right\} } \right) \), if \(\mu (t) < \alpha \); and (ii) the tight upper bound of \(\Pr [{S(t)} \le \alpha ]\) is \(O\left( {\exp \left\{ { - n\ell \left( {\frac{\alpha }{{nsup}},\frac{{\mu (t)}}{{nsup}}} \right) } \right\} } \right) \), if \(\mu (t) > \alpha \), where \(\Pr [X]\) is the probability of random event \(X,\, S(t)\) is the sum of the monitored area at time \(t,\, n\) is the number of the sensor nodes, \(sup\) is the upper bound of sensed data, \( \mu (t)\) is the expectation of \(S(t)\), and \(\ell ({x_1},{x_2}) = {x_1}\ln \left( {\frac{{{x_1}}}{{{x_2}}}} \right) + (1 - {x_1})\ln \left( {\frac{{1 - {x_1}}}{{1 - {x_2}}}} \right) \). An instant \((\alpha ,\tau )\)-monitoring scheme is then developed based on the upper bound. Moreover, approximate continuous \((\alpha , \tau )\)-monitoring is investigated. We prove that the probability of false negative alarm is \(\delta \), if the sample size is Open image in new window for a given precision requirement, where Open image in new window is the Open image in new window fractile of a standard normal distribution. Finally, the performance of the proposed algorithms is validated through experiments.     

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis

Patterned self-assembly tile set synthesis (pats) aims at minimizing the number of distinct DNA tile types used to self-assemble a given rectangular color pattern. For an integer k, k-pats is the subproblem of pats that restricts input patterns to those with at most k colors. We give an efficient Open image in new window verifier, and based on that, we establish a manually-checkable proof for the NP-hardness of 11-pats; the best previous manually-checkable proof is for 29-pats.     

The corporate library as a source of new technology

In an inflationary economy of declinin R

D expenditures, effective transfer of innovative ideas from the literature to the laboratory can significantly complement an R

D budget. This paper discusses an efective library management organization and practical mechanisms for improving technology transfer from the corporate library. Experience at Sanders Associates Inc. with the techniques presented had been most favourable. Substantial savings in R

D dollars have been realized.     

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3

Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring. MSC: 05C15     

Fast algorithms for computing the tripartition-based distance between phylogenetic networks

Consider two phylogenetic networks and ’ of size n. The tripartition-based distance finds the proportion of tripartitions which are not shared by and ’. This distance is proposed by Moret et al. (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an -time algorithm to compute this distance, where h is the number of hybrid nodes in and ’ while k is the maximum number of hybrid nodes among all biconnected components in and ’. Note that $k \ll h \ll n$ in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an $O(n)$-time algorithm for comparing two galled-trees. We also give an -time algorithm for comparing a galled-tree with another general network, where h and k are the number of hybrid nodes in the latter network and its biggest biconnected component respectively.     

Construction of the nearest neighbor embracing graph of a point set

This paper gives optimal algorithms for the construction of the Nearest Neighbor Embracing Graph (NNE-graph) of a given point set V of size n in the k-dimensional space (k-D) for k = 2,3. The NNE-graph provides another way of connecting points in a communication network, which has lower expected degree at each point and shorter total length of connections with respect to those using Delaunay triangulation. In fact, the NNE-graph can also be used as a tool to test whether a point set is randomly generated or has some particular properties. We show that in 2-D the NNE-graph can be constructed in optimal time in the worst case. We also present an time algorithm, where d is the -th largest degree in the utput NNE-graph. The algorithm is optimal when . The algorithm is also sensitive to the structure of the NNE-graph, for instance when , the number of edges in NNE-graph is bounded by for any value g with . We finally propose an time algorithm for the problem in 3-D, where d and are the -th largest vertex degree and the largest vertex degree in the NNE-graph, respectively. The algorithm is optimal when the largest vertex degree of the NNE-graph is .     

Center and Distinguisher for Strings with Unbounded Alphabet

Consider two sets and of strings of length L with characters from an unbounded alphabet , i.e., the size of is not bounded by a constant and has to be taken into consideration as a parameter for input size. A closest string s* of is a string that minimizes the maximum of Hamming¹ distance(s, s*) over all string s : s . In contrast, a farthest string t* from maximizes the minimum of Hamming distance(t*,t) over all elements t: t . A distinguisher of from is a string that is close to every string in and far away from any string in . We obtain polynomial time approximation schemes to settle the above problems.     

Domination and total domination in complementary prisms

Let G be a graph and be the complement of G. The complementary prism of G is the graph formed from the disjoint union of G and by adding the edges of a perfect matching between the corresponding vertices of G and . For example, if G is a 5-cycle, then is the Petersen graph. In this paper we consider domination and total domination numbers of complementary prisms. For any graph G, and , where γ(G) and γ _t (G) denote the domination and total domination numbers of G, respectively. Among other results, we characterize the graphs G attaining these lower bounds. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.     

Minimum ε-equivalent Circuit Size Problem

For a Boolean function f given by its truth table (of length ) and a parameter s the problem considered is whether there is a Boolean function g -equivalent to f, i.e., , and computed by a circuit of size at most s. In this paper we investigate the complexity of this problem and show that for specific values of it is unlikely to be in P/poly. Under the same assumptions we also consider the optimization variant of the problem and prove its inapproximability.     

A Probabilistic Analysis of the Capacitated Facility Location Problem

The solution value of a stochastic version of the capacitated facility location problem is studied. It is shown that, for large numbers of customers n, the value of can be closely approximated by , where the constant is identified as a function of the parameters of the underlying stochastic model. Furthermore, an extensive probabilistic analysis is performed on the difference that includes an exponential inequality on the tail distribution, a classification of the speed of convergence and a central limit theorem.     

On-line production order scheduling with preemption penalties

This paper studies the on-line production order scheduling problem where each preemption causes a penalty, and the objective is to maximize the net profit, i.e., the total weights of completed orders minus the total penalties caused by preemptions. Two greedy strategies are shown to be at best and -competitive respectively, where Δ is the ratio between the longest and shortest length of order. After that we mainly present an improved strategy, named WAL, which takes advantage of the knowledge of Δ and is proved to be -competitive for Δ > 9. Furthermore, two lower bounds for deterministic strategies, and 6.33, are given for the cases of nonuniform and uniform length respectively. This research is supported by NSF of China under Grants 70471035, 70525004, 70121001 and 70602031.     

Improved algorithms for largest cardinality 2-interval pattern problem

The 2-INTERVAL PATTERN problem is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are R-comparable, where model . The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an O(n{log} n +L) algorithm is proposed for the case , where is the total length of all 2-intervals (density d is the maximum number of 2-intervals over any point). This improves previous O(n ²log n) algorithm. Secondly, we use dynamic programming techniques to obtain an O(nlog n + dn) algorithm for the case R = { <, ⊏ }, which improves previous O(n ²) result. Finally, we present another algorithm for the case with disjoint support(interval ground set), which improves previous O(n ²□n) upper bound. A preliminary version of this article appears in Proceedings of the 16th Annual International Symposium on Algorithms and Computation, Springer LNCS, Vol. 3827, pp. 412–421, Hainan, China, December 19–21, 2005.     

On zero error algorithms having oracle access to one query

It is known that (Cai, 2001). The reverse direction of whether ZPP^NP is contained in remains open. We show that if the zero-error algorithm is allowed to ask only one query to the NP oracle (for any input and random string), then it can be simulated in . That is, we prove that . Next we consider whether the above result can be improved as and point out a difficulty in doing so. Via a simple proof, we observe that BPP ⊆ ZPP^NP[1] (a result implicitly proven in some prior work). Thus, achieving the above improvement would imply BPP ⊆ P^NP, settling a long standing open problem. We then argue that the above mentioned improvement can be obtained for the next level of the polynomial time hierarchy. Namely, we prove that . On the other hand, by adapting our proof of our main result it can be shown that . For the purpose of comparing these two results, we prove that . We conclude by observing that the above claims extend to the higher levels of the hierarchy: for k ≥ 2, and . Research supported in part by NSF grant CCR-0208013. A preliminary version of the paper was presented at COCOON′05 Cai and Chakaravarthy (2005). Part of the research was conducted while the author was at the University of Wisconsin, Madison.     

The inverse 1-maxian problem with edge length modification

We consider the problem of modifying the lengths of the edges of a graph at minimum cost such that a prespecified vertex becomes a 1-maxian with respect to the new edge lengths. The inverse 1-maxian problem with edge length modification is shown to be strongly -hard and remains weakly -hard even on series-parallel graphs. Moreover, a transformation of the inverse 1-maxian problem with edge length modification on a tree to a minimum cost circulation problem is given which solves the original problem in . This research has been supported by the Austrian Science Fund (FWF) Project P18918-N18.     

Some extremal properties of the multiplicatively weighted Harary index of a graph

Let \(G=(V_G, E_G)\) be a simple connected graph. The multiplicatively weighted Harary index of \(G\) is defined as \(H_M(G)=\sum _{\{u,v\}\subseteq V_G}\delta _G(u)\delta _G(v)\frac{1}{d_G(u,v)},\) where \(\delta _G(u)\) is the vertex degree of \(u\) and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G.\) This novel invariant is in fact the modification of the Harary index in which the contributions of vertex pairs are weighted by the product of their degrees. Deng et al. (J Comb Optim 2014, doi: 10.1007/s10878-013-9698-5) determined the extremal values on \(H_M\) of graphs among \(n\)-vertex trees (resp. unicyclic graphs). In this paper, as a continuance of it, the monotonicity of \(H_M(G)\) under some graph transformations were studied. Using these nice mathematical properties, the extremal graphs among \(n\)-vertex trees with given graphic parameters, such as pendants, matching number, domination number, diameter, vertex bipartition, et al. are characterized, respectively. Some sharp upper bounds on the multiplicatively weighted Harary index of trees with given parameters are determined.     

Nonparametric Predictive Inference for Exposure Assessment

Exposure assessment for food and drink consumption requires the combining of information about people's consumption of products with concentration data sets to provide predictions for chemical intake by humans. In this article, we present a method called nonparametric predictive inference (NPI) for exposure assessment. NPI is a distribution‐free method relying only on Hill's assumption . Effectively, is a postdata exchangeability assumption, which is a natural starting point for nonparametric statistics. For further discussion we refer to works by Hill and Coolen. We illustrate how NPI can be implemented to produce predictions for an individual's exposure based on consumption, body weight, and concentration data. NPI has the advantage that we do not have to assume a distribution to implement it. There may, however, be information available to suggest a distribution for a random quantity. Therefore, we present an NPI‐Bayes hybrid method where this information can be taken into account by using Bayesian methods while using NPI for the other random quantities in the model.     

Paired-domination in generalized claw-free graphs

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998) 199–206). A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. If G does not contain a graph F as an induced subgraph, then G is said to be F-free. Haynes and Slater (Networks 32 (1998) 199–206) showed that if G is a connected graph of order , then and this bound is sharp for graphs of arbitrarily large order. Every graph is -free for some integer a ≥ 0. We show that for every integer a ≥ 0, if G is a connected -free graph of order n ≥ 2, then with infinitely many extremal graphs.     

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Given a finite set V and a set function , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in time, where is the time to compute the value of f(X) for a subset .