Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

Analysis of queueing policies in QoS switches

It is widely accepted that next-generation networks will provide guaranteed services, in contrast to the “best effort” approach today. We study and analyze queueing policies for network switches that support the QoS (Quality of Service) feature. One realization of the QoS feature is that packets are not necessarily all equal, with some having higher priorities than the others. We model this situation by assigning an intrinsic value to each packet. In this paper we are concerned with three different queueing policies: the nonpreemptive model, the FIFO preemptive model, and the bounded delay model. We concentrate on the situation where the incoming traffic overloads the queue, resulting in packet loss. The objective is to maximize the total value of packets transmitted by the queueing policy. The difficulty lies in the unpredictable nature of the future packet arrivals. We analyze the performance of the online queueing policies via competitive analysis, providing upper and lower bounds for the competitive ratios. We develop practical yet sophisticated online algorithms (queueing policies) for the three queueing models. The algorithms in many cases have provably optimal worst-case bounds. For the nonpreemptive model, we devise an optimal online algorithm for the common 2-value model. We provide a tight logarithmic bound for the general nonpreemptive model. For the FIFO preemptive model, we improve the general lower bound to 1.414, while showing a tight bound of 1.434 for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also show an improved lower bound of 1.618 for the 2-variable bounded delay model, matching the previously known upper bound.     

The Injective Spectrum of a Noncommutative Space

For a noncommutative space X, we study Inj(X), the set of isomorphism classes of indecomposable injective X-modules. In particular, we look at how this set, suitably topologized, can be viewed as an underlying “spectrum” for X. As applications we discuss noncommutative notions of irreducibility and integrality, and a way of associating an integral subspace of X to each element of Inj(X) which behaves like a “weak point.”     

Best Interpolatory Approximation in Normed Linear Spaces

A theory of best approximation with interpolatory contraints from a finite-dimensional subspaceMof a normed linear spaceXis developed. In particular, to eachxX, best approximations are sought from a subsetM(x) ofMwhichdependson the elementxbeing approximated. It is shown that this “parametric approximation” problem can be essentially reduced to the “usual” one involving a certainfixedsubspaceM₀ofM. More detailed results can be obtained when (1) Xis a Hilbert space, or (2) Mis an “interpolating subspace” ofX(in the sense of [1]).     

Browder’s Theorems through Localized SVEP

A bounded linear operator T ∈ L(X) on aBanach space X is said to satisfy “Browder’s theorem” if the Browder spectrum coincides with the Weyl spectrum. T ∈ L(X) is said to satisfy “a-Browder’s theorem” if the upper semi-Browder spectrum coincides with the approximate point Weyl spectrum. In this note we give several characterizations of operators satisfying these theorems. Most of these characterizations are obtained by using a localized version of the single-valued extension property of T. In the last part we shall give some characterizations of operators for which “Weyl’s theorem” holds.     

Confinement of the infrared divergence for the Mumford process

The Mumford process X is a stochastic distribution modulo constant and cannot be defined as a stochastic distribution invariant in law by dilations. We present two expansions of X—using wavelet bases—in X=X₀+X₁ which allow us to confine the divergence on the “small term” X₁ and which respect the invariance in law by dyadic dilations of the process.     

On almost Chebyshev subspaces

A closed subspace F in a Banach space X is called almost Chebyshev if the set of x ε X which fail to have unique best approximation in F is contained in a first category subset. We prove, among other results, that if X is a separable Banach space which is either locally uniformly convex or has the Radon-Nikodym property, then “almost all” closed subspaces are almost Chebyshev.     

Effacement des dérivations et spectres premiers des algèbres quantiques

Given any (commutative) field k and any iterated Ore extension R=k[X₁][X₂;σ₂,δ₂][X_N;σ_N,δ_N] satisfying some suitable assumptions, we construct the so-called “Derivative-Elimination Algorithm.” It consists of a sequence of changes of variables inside the division ring F=Fract(R), starting with the indeterminates (X₁,…,X_N) and terminating with new variables (T₁,…,T_N). These new variables generate some quantum-affine space such that . This algorithm induces a natural embedding which satisfies the following property:

Full-size image

. We study both the derivative-elimination algorithm and natural embedding and use them to produce, for the general case, a (common) proof of the “quantum Gelfand–Kirillov” property for the prime homomorphic images of the following quantum algebras: , (wW), R_q[G] (where G denotes any complex, semi-simple, connected, simply connected Lie group with associated Lie algebra and Weyl group W), quantum matrices algebras, quantum Weyl algebras and quantum Euclidean (respectively symplectic) spaces. Another application will be given in [G. Cauchon, J. Algebra, to appear]: In the general case, the prime spectrum of any quantum matrices algebra satisfies the normal separation property.     

Subtractive Categories

We introduce a notion of a subtractive category. It generalizes the notion of a pointed subtractive variety of universal algebras in the sense of A. Ursini. Subtractive categories are closely related to Mal’tsev and additive categories: (i) a category C with finite limits is a Mal’tsev category if and only if for every object X in C the category Pt(X)=((X,1_X)↓(C↓X)) of “points over X” is subtractive; (ii) a pointed category C with finite limits is additive if and only if C is subtractive and half-additive.Mathematics Subject Classifications (2000) 18C99, 18E05, 08B05.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

Performance analysis of AAL multiplexer with CBR traffic and bursty traffic

This paper models and evaluates the AAL multiplexer to analyze AAL protocol in ATM networks. We consider an AAL multiplexer in which a single periodically deterministic CBR traffic stream and several variable size bursty background traffic streams are multiplexed and one ATM cell stream goes out. We model the AAL multiplexer as aB ^X +D/D/1/K queue and analyze this queueing system. We represent various performance measures such as loss probability and waiting time in the basis of cell and packet.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

k-Best Solutions under Distance Constraints in Valuated -Matroids

In discrete maximization problems one usually wants to find an optimal solution. However, in several topics like “alignments,” “automatic speech recognition,” and “computer chess” people are interested to find thekbest solutions for somek ≥ 2. We demand that theksolutions obey certain distance constraints to avoid that thekalternatives are too similar. Several results for valuated -matroids are presented, some of them concerning time complexity of algorithms.     

On the ω-problem for some types of non-metrizable spaces

The ω-problem on a topological space X consists in finding out whether there exists a function whose oscillation is equal to a given upper semi-continuous (USC) function f:X→[0,∞] vanishing at isolated points of X. If such F exists, we call it an ω-primitive for f. Unlike the case of metrizable spaces, an ω-primitive need not exist if X is not metrizable. We study the ω-problem for f taking the value ∞ in the case of ordinal space, products of regular “constancy” spaces and the wedge sums of such spaces. Some open problems are formulated.     

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”     

Nonmonotone, nonlinear evolution inclusions

In this paper, we consider nonlinear evolution problems, defined on an evolution triple of spaces, driven by a nonmonotone operator, and with a perturbation term which is multivalued. We prove existence theorems for the cases of a convex and of a nonconvex valued perturbation term which is defined on all of T × H or only on T × X with values in H or even in X^* (here X - H - X^* is the evolution triple). Also, we prove the existence of extremal solutions, and for the “monotone” problem we have a strong relaxation theorem. Some examples of nonlinear parabolic problems are presented.     

Reverse mathematics and well-ordering principles: A pilot study

The larger project broached here is to look at the generally sentence “if X is well-ordered then f(X) is well-ordered”, where f is a standard proof-theoretic function from ordinals to ordinals. It has turned out that a statement of this form is often equivalent to the existence of countable coded ω-models for a particular theory T_f whose consistency can be proved by means of a cut elimination theorem in infinitary logic which crucially involves the function f. To illustrate this theme, we prove in this paper that the statement “if X is well-ordered then ε_X is well-ordered” is equivalent to . This was first proved by Marcone and Montalban [Alberto Marcone, Antonio Montalbán, The epsilon function for computability theorists, draft, 2007] using recursion-theoretic and combinatorial methods. The proof given here is principally proof-theoretic, the main techniques being Schütte’s method of proof search (deduction chains) [Kurt Schütte, Proof Theory, Springer-Verlag, Berlin, Heidelberg, 1977] and cut elimination for a (small) fragment of .     

Queueing networks with dependent nodes and concurrent movements

Classical queueing network processes are useful for modeling the movement of discrete units in a network in which the nodes operate independently, the routing of units is independent of the congestion, only one unit moves at a time and its equilibrium distribution is a well-understood product form. Actual networks, however, typically have dependent nodes and concurrent movement of units. Imagine the dependencies associated with the network movements of telephone calls, manufacturing material, computer data packets, messages in a parallel-processing simulation, etc. A second generation of queueing network processes is beginning to evolve for modeling such “intelligent” networks with dependent nodes and concurrent movements. This paper describes the following fundamental processes that have been developed in this regard:

? A basic queueing network process for dependent nodes and single-unit movements. Examples include the classical Jackson, BCMP, Kelly and Kelly-Whittle networks and networks with interacting subpopulations.

? Reversible queueing network processes for dependent nodes and concurrent movements. An example is a multivariate, compound birth-death process.

? Miscellaneous partially balanced queueing networks. Examples include extensions of the basic network processes and weakly coupled and quasi-reversible networks.

     

Fluid models of congestion collapse in overloaded switched networks

We consider a switched network (i.e. a queueing network in which there are constraints on which queues may be served simultaneously), in a state of overload. We analyse the behaviour of two scheduling algorithms for multihop switched networks: a generalized version of max-weight, and the α-fair policy. We show that queue sizes grow linearly with time, under either algorithm, and we characterize the growth rates. We use this characterization to demonstrate examples of congestion collapse, i.e. cases in which throughput drops as the switched network becomes more overloaded. We further show that the loss of throughput can be made arbitrarily small by the max-weight algorithm with weight function f(q)=q ^α as α→0.     

A graph search algorithm for indoor pursuit/evasion

Using concepts from both robotics and graph theory, we formulate the problem of indoor pursuit/evasion in terms of searching the nodes of a graph for a mobile evader. We present the IGNS (Iterative Greedy Node Search) algorithm, which performs offline guaranteed search (i.e. no matter how the evader moves, it will eventually be captured). Furthermore, the algorithm produces an internal search (the searchers move only along the edges of the graph; “teleporting” is not used) and exploits non-monotonicity, extended visibility and finite evader speed to reduce the number of searchers required to clear an environment. We present search experiments for several indoor environments, in all of which the algorithm succeeds in clearing the graph (i.e. capturing the evader).