An optimal strategy for a conflict resolution problem

Relevant to the design of multiple access protocols is the problem of finding the largest of N i.i.d. numbers X₁,…,X_N uniformly distributed over [0,1] using the minimum number of questions of the following type. We pick a set A(1) [0, 1] and ask which X_i ε A(1). Depending on the response, we pick another subset A(2) and ask which X_i ε A(2), and so on, until we identify the largest X_i. It is shown that the optimum sequence of questions must be of the type A(k) = (a(k), 1]; the best sequence {a(k)} can then be determined by dynamic programming following the work of Arrow, Pesotchinsky and Sobel.     

Minimum polygonal separation

In this paper we study the problem of polygonal separation in the plane, i.e., finding a convex polygon with minimum number k of sides separating two given finite point sets (k-separator), if it exists. We show that for k = Θ(n), Ω(n log n) is a lower bound to the running time of any algorithm for this problem, and exhibit two algorithms of distinctly different flavors. The first relies on an O(n log n)-time preprocessing task, which constructs the convex hull of the internal set and a nested star-shaped polygon determined by the external set; the k-separator is contained in the annulus between the boundaries of these two polygons and is constructed in additional linear time. The second algorithm adapts the prune-and-search approach, and constructs, in each iteration, one side of the separator; its running time is O(kn), but the separator may have one more side than the minimum.     

Optimal Content Location in Multicast Based Overlay Networks with Content Updates

The architecture of overlay networks should support high-performance and high-scalability at low costs. This becomes more crucial when communication, storage costs as well as service latencies grow with the exploding amounts of data exchanged and with the size and span of the overlay network. For that end, multicast methodologies can be used to deliver content from regional servers to end users, as well as for the timely and economical synchronization of content among the distributed servers. Another important architectural problem is the efficient allocation of objects to servers to minimize storage, delivery and update costs. In this work, we suggest a multicast based architecture and address the optimal allocation and replication of dynamic objects that are both consumed and updated. Our model network includes consumers which are served using multicast or unicast transmissions and media sources (that may be also consumers) which update the objects using multicast communication. General costs are associated with distribution (download) and update traffic as well as the storage of objects in the servers. Optimal object allocation algorithms for tree networks are presented with complexities of O(N) and O(N ²) in case of multicast and unicast distribution respectively. To our knowledge, the model of multicast distribution combined with multicast updates has not been analytically dealt before, despite its popularity in the industry.     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Lower Bounds for Dynamic Algebraic Problems

We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x₁,…, x_n)=(y₁, …, y_m) is an algebraic problem, we consider serving online requests of the form “change input x_i to value v” or “what is the value of output y_i?” We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance, history dependent algebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Ω(n) bounds for dynamic matrix–vector product, dynamic matrix multiplication, and dynamic discriminant and an Ω( ) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif and Tate's O( ) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint, and matrix inverse and an Ω( ) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the setting of dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an Ω((log n)²/log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.     

On decoupling the H-optimal sensitivity problem for products of plants

In this note we show how to solve the H^∞-optimal sensitivity problem for a SISO plant P(s) = P₁(s)P₂(s), given the solutions for P₁(s), P₂(s). This allows us to solve the problem for systems of the form e^−hsP₀(s), where P₀(s) is the transfer function of a stable, LTI, finite dimensional system.     

On the weighted sensitivity minimization problem for delay systems

We consider the H^∞-optimal sensitivity problem for delay systems. In particular, we consider computation of μ:= inf {|W-φq|_∞ : q ε H^∞(j )} where W(s) is any function in RH^∞(j ), and φ in H^∞(j ) is any inner function. We derive a new explicit solution in the pure delay case where φ = e^−sh, h > 0.     

Many-step two-person games with a fixed sequence of moves under aggregated information on partner’s choice

A many-step two-person game is studied with a fixed sequence of moves under aggregated information on every move at the decision making instant and on the choice of player 2 at the current move. Player 1, knowing this information at every step i, first chooses a strategy x_i(·) = (x₁(·),...,x_n(·)), i = , and informs it for n moves to player 2 at the beginning of the game. His maximal guaranteed result and the corresponding optimal (-optimal) strategy are determined. Such games under complete (nonaggregated) information are formulated and a compact expression for the strategy of player 1 is derived.Translated from Avtomatika i Telemekhanika, No. 2, 2005, pp. 108–114.Original Russian Text Copyright © 2005 by Aliev, Kononenko.This work was supported by the Russian Foundation for Basic Research, project no. 99-01-00791.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

On the expected complexity of distributed selection

In this paper, the expected communication complexity of the distributed selection problem is investigated; i.e., the problem of selecting the Kth smallest element in a file of N records distributed among d sites of a communication network. Letting Δ = Min{K, N + 1 − K}, it is shown that O(d(log Δ + log d) and O(log Δ + log d) communication activities suffice on the average for point-to-point and shout-echo networks, respectively, improving the existing bounds. These results do not rely on any assumption on the distribution of the file elements among the network sites.     

A multiagent framework for coordinated parallel problem solving

Today’s organizations, under increasing pressure on the effectiveness and the increasing need for dealing with complex tasks beyond a single individual’s capabilities, need technological support in managing complex tasks that involve highly distributed and heterogeneous information sources and several actors. This paper describes CoPSF, a multiagent system middle-ware that simplifies the development of coordinated problem solving applications while ensuring standard compliance through a set of system services and agents. CoPSF hosts and serves multiple concurrent teams of problem solving contributing both to the limitation of communication overheads and to the reduction of redundant work across teams and organizations. The framework employs (i) an interleaved task decomposition and allocation approach, (ii) a mechanism for coordination of agents’ work, and (iii) a mechanism that enables synergy between parallel teams.     

Dynamic Hotlinks

Consider a directed rooted tree T=(V,E) representing a collection V of n web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each web page i carries a weight w _i representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendants, we are interested in minimizing the expected number of steps needed to visit pages from the home page. We give the first linear time algorithm for assigning hotlinks so that the number of steps to access a page i from the root of the tree reaches the entropy bound, i.e. is at most O(log (W/w _i )) where W=∑ _i∈T w _i . The best previously known algorithm for this task runs in time O(n ²). We also give the first efficient data structure for maintaining hotlinks when nodes are added, deleted or their weights modified, in amortized time O(log (W/w _i )) per update. The data structure can be made adaptive, i.e. reaches the entropy bound in the amortized sense without knowing the weights w _i in advance.     

A numerical method for deadbeat control of generalized state-space systems

In this paper we give a new numerical method for constructing a rank m correction BF to an n × n matrix A, such that the generalized eigenvalues of λE−(A+BF) are all at λ = 0. In the control literature, this problem is known as ‘deadbeat control’ of a generalized state-space system Ex_i+1 = Ax_i + Bu_i, whereby the matrix F is the ‘feedback matrix’ to be constructed.     

Parallel solution of recurrences on a tree machine

The recurrencex _o =a _o x _i =a _i+b _i x _i–1,i = 1, 2,...,n–1 requiresO(n) operations on a sequential computer. Elegant parallel solutions exist, however, that reduce the complexity toO(logN) usingNn processors. This paper discusses one such solution, designed for a tree-structured network of processors.A tree structure is ideal for solving recurrences. It takes exactly one sweep up and down the tree to solve any of several classes of recurrences, thus guaranteeing a solution inO(logN) time for a tree withNn leaf nodes. Ifn exceedsN, the algorithm efficiently pipelines the operation and solves the recurrence inO(n/N + logN) time.     

A Compiler-Directed Approach to Network Latency Reduction for Distributed Shared Memory Multiprocessors

In distributed shared memory multiprocessor systems, parallel tasks communicate through sharing memory data. As the system size increases, such communication cost becomes the main factor that limits the overall parallelism and performance. In this paper, we propose a new solution to the problem through judiciously managing the relevant resource, namely, the shared data and the interconnection network (IN) through which the sharing is carried out. In this approach, communication cost is minimized by means of data migration/allocation which is based on analyzing general layered task graphs, sharing behavior of parallel tasks, and network topology. Our method is not applicable for read only variables. Further, for the time being, the usefulness of the method is limited to multiprocessors where no cache coherence mechanism is implemented. Four typical interconnection topologies for multiprocessors are considered, namely, shared-bus, hierarchical-bus, 2-D mesh, and fat-tree structures. Efficient data allocation algorithms for each of the four network topologies are developed that make decision on data allocation/migration at the compile time. The complexity of one algorithm isO(np) for shared-bus andO(n²p) for the remaining three in a system withnprocessors executing ap-layer task graph for one shared variable. We have also given an algorithm to determine optimal allocation/migration scheme for multiple shared variables. However, the cost of the algorithm become prohibitive when the number of shared variables is high. Therefore, a heuristic of low complexity is suggested. The heuristic is optimal for some topologies.     

Compact Recognizers of Episode Sequences

Given two strings X=a₁…a_n and P=b₁…b_m over an alphabet Σ, the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O(n log |Σ|) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log |Σ| character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O(n²) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O(n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O(∑_i=1^mrocc_i·i) or O(n+∑_i=1^mrocc_i·i· log n), depending on whether the alphabet is fixed or arbitrary, where rocc_i is the number of distinct minimal substrings of X having b₁…b_i as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.     

Spectral properties of infinite-dimensional closed-loop systems

We consider feedback systems obtained from infinite-dimensional well-posed linear systems by output feedback. Thus, our framework allows for unbounded control and observation operators. Our aim is to investigate the relationship between the open-loop system, the feedback operator K and the spectrum (in particular, the eigenvalues and eigenvectors) of the closed-loop generator A^K. We give a useful characterization of that part of the spectrum σ(A^K) which lies in the resolvent set of A, the open-loop generator, via the “characteristic equation” involving the open-loop transfer function. We show that certain points of σ(A) cannot be eigenvalues of A^K if the input and output are scalar (so that K is a number) and K≠0. We devote special attention to the case when the output feedback operator K is compact. It is relatively easy to prove that in this case, σ_e(A), the essential spectrum of A, is invariant, that is, it is equal to σ_e(A^K). A related but much harder problem is to determine the largest subset of σ(A) which remains invariant under compact output feedback. This set, which we call the immovable spectrum of A, strictly contains σ_e(A). We give an explicit characterization of the immovable spectrum and we investigate the consequences of our results for a certain class of well-posed systems obtained by interconnecting an infinite chain of identical systems.     

Approximate fixed point sequence for a finite family of asymptotically pseudocontractive mappings

Let E be a real Banach space and K be a nonempty, closed, convex, and bounded subset of E. Let T_i:K→K, i=1,2,…,N, be N uniformly L-Lipschitzian, uniformly asymptotically regular with sequences {ε_n}, and asymptotically pseudocontractive mappings with sequences , where {ε_n} and , i=1,2,…,N, satisfy certain mild conditions. Let a sequence {x_n} be generated from x₁K by

for all integers n1, where T_n=T_n(modN), {u_n} be a sequence in K, and {λ_n}, {θ_n} and {μ_n} are three real sequences in [0,1] satisfying appropriate conditions; then x_n−T_lx_n→0 as n→∞ for each l{1,2,…,N}.     

On Parallel Selection and Searching in Partial Orders: Sorted Matrices

Parallel algorithms for the problems of selection and searching on sorted matrices are formulated. The selection algorithm takesO(lognlog lognlog*n) time withO(n/lognlog*n) processors on an EREW PRAM. This algorithm can be generalized to solve the selection problem on a set of sorted matrices. The searching algorithm takesO(log logn) time withO(n/log logn) processors on a Common CRCW PRAM, which is optimal. We show that no algorithm using at mostnlog^cnprocessors,c≥ 1, can solve the matrix search problem in time faster than Ω(log logn) and that Ω(logn) steps are needed to solve this problem on any model that does not allow concurrent writes.