Heavy traffic analysis of roving server networks

This article studies the heavy-traffic (HT) behavior of queueing networks with a single roving server. External customers arrive at the queues according to independent renewal processes and after completing service, a customer either leaves the system or is routed to another queue. This type of customer routing in queueing networks arises very naturally in many application areas (in production systems, computer- and communication networks, maintenance, etc.). In these networks, the single most important characteristic of the system performance is oftentimes the path time, i.e., the total time spent in the system by an arbitrary customer traversing a specific path. The current article presents the first HT asymptotic for the path-time distribution in queueing networks with a roving server under general renewal arrivals. In particular, we provide a strong conjecture for the system’s behavior under HT extending the conjecture of Coffman et al.^{[8 Coffman, Jr, E. G.; Puhalskii, A. A.; Reiman, M. I,. Polling systems with zero switchover times: A heavy-traffic averaging principle. Ann. App. Prob. 1995, 5(3), 681–719.[Crossref], [Web of Science ®] [Google Scholar],9 Coffman, Jr., E. G.; Puhalskii, A. A.; Reiman, M. I,. Polling systems in heavy-traffic: A Bessel process limit. Math. Oper. Res. 1998, 23, 257–304.[Crossref], [Web of Science ®] [Google Scholar]]} to the roving server setting of the current article. By combining this result with novel light-traffic asymptotics, we derive an approximation of the mean path time for arbitrary values of the load and renewal arrivals. This approximation is not only highly accurate for a wide range of parameter settings, but is also exact in various limiting cases.     

On Ring Grooming in optical networks

An instance I of Ring Grooming consists of m sets A ₁,A ₂,…, A _m from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P ₁ , P ₂, …,P _k } of {1, 2, …, m} such that for each 1 ≤ i ≤ k and is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition of {1,2,…,m} such that | P _i | ≤ g for each and is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5 when g = 4, at most 2.5 when g = 8, and at most in general while it is conjectured to be at most . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m ^g . Work supported by a DIMACS postdoctoral fellowship.     

A Modular CDF Approach for the Approximation of Percentiles

This article describes a method for computing approximate statistics for large data sets, when exact computations may not be feasible. Such situations arise in applications such as climatology, data mining, and information retrieval (search engines). The key to our approach is a modular approximation to the cumulative distribution function (cdf) of the data. Approximate percentiles (as well as many other statistics) can be computed from this approximate cdf. This enables the reduction of a potentially overwhelming computational exercise into smaller, manageable modules. We illustrate the properties of this algorithm using a simulated data set. We also examine the approximation characteristics of the approximate percentiles, using a von Mises functional type approach. In particular, it is shown that the maximum error between the approximate cdf and the actual cdf of the data is never more than 1% (or any other preset level). We also show that under assumptions of underlying smoothness of the cdf, the approximation error is much lower in an expected sense. Finally, we derive bounds for the approximation error of the percentiles themselves. Simulation experiments show that these bounds can be quite tight in certain circumstances.     

Regression with an infinite number of observations applied to estimating the parameters of the stable distribution using the empirical characteristic function

ABSTRACT

The parameters of stable law parameters can be estimated using a regression based approach involving the empirical characteristic function. One approach is to use a fixed number of points for all parameters of the distribution to estimate the characteristic function. In this work the results are derived where all points in an interval is used to estimate the empirical characteristic function, thus least squares estimators of a linear function of the parameters, using an infinite number of observations. It was found that the procedure performs very good in small samples.     

Tree edge decomposition with an application to minimum ultrametric tree approximation

A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.     

A simple linear time approximation algorithm for multi-processor job scheduling on four processors

Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P ₄|fix|C _max, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.     

Approximation Algorithms for Certain Network Improvement Problems

We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph G = (V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function ce (t) that specifies the cost of upgrading the edge by an amount t. A reduction strategy specifies for each edge e the amount by which the length (e) is to be reduced. In the node based upgrading model, a node v can be upgraded at an expense of c(v). Such an upgrade reduces the delay of each edge incident on v. For a given budget B, the goal is to find an improvement strategy such that the total cost of reduction is at most the given budget B and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint.After providing a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approximability of network improvement problems.     

Two-step and likelihood methods for joint models of longitudinal and survival data

We compare the commonly used two-step methods and joint likelihood method for joint models of longitudinal and survival data via extensive simulations. The longitudinal models include LME, GLMM, and NLME models, and the survival models include Cox models and AFT models. We find that the full likelihood method outperforms the two-step methods for various joint models, but it can be computationally challenging when the dimension of the random effects in the longitudinal model is not small. We thus propose an approximate joint likelihood method which is computationally efficient. We find that the proposed approximation method performs well in the joint model context, and it performs better for more “continuous” longitudinal data. Finally, a real AIDS data example shows that patients with higher initial viral load or lower initial CD4 are more likely to drop out earlier during an anti-HIV treatment.     

Parental responsibilities: Reformulating the paradigm for parent–child relationships Part 2: Who has responsibilities to children and what are these responsibilities?

This is the second part of an article, Part 1 of which proposes the paradigm of parental responsibilities to replace the discourse of rights, custody, and visitation. This Part describes the scope of parental responsibilities; who, alongside or instead of the biological parents, may have parental responsibilities vis-à-vis the child; the roles of grandparents and members of the extended family, and partners of parents, are described. The principal categories of parenting tasks are described in detail. I also show how the concept of parental responsibilities is essential for properly dealing with children in need of protection, and how the paradigm applies to courts that deal with proceedings involving children.     

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.