Search

In this paper, we discuss a variational inequality problem with the gradient of a nonconvex objective function in which the constraint set composed of the absolute set and the subsidiary sets is not feasible. We formulate a compromise solution of the problem by using a solution to a variational inequality for the gradient over a subset of the absolute set with the elements closest to the subsidiary sets in terms of the norm. The objective of this paper is to enable us to discuss a network bandwidth allocation problem with a nonconcave utility function in which the compoundable constraints about the preferable transmission rate fall in the infeasible region. For such a bandwidth allocation, the ideal bandwidth must be quickly shared among traffic sources so as to satisfy the capacity constraints (absolute constraints) and all sources' demands regarding the transmission rate (subsidiary constraints) as much as possible. Iterative algorithms for the bandwidth allocation should thus not involve auxiliary optimization problems or complicated computations. Here, we devise an algorithm based on an iterative technique for triple-hierarchical constrained nonconvex optimization to achieve the optimal bandwidth allocation. Numerical examples for the bandwidth allocation demonstrate the effectiveness and convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper describes a scheme to implement a shared address space of size m on an n-node mesh, with m polynomial in n, where each mesh node hosts a processor and a memory module. At the core of the simulation is a hierarchical memory organization scheme (HMOS), which governs the distribution of the shared variables, each replicated into multiple copies, among the memory modules, through a cascade of bipartite graphs. Based on the expansion properties of such graphs, we devise a protocol that accesses any n-tuple of shared variables in worst-case time O(n[SUP1/2+n]), for any constant n > 0, using O(1/η[SUP1.59) copies per variable, or in worst-case time O(n[SUP1/2]log n), using O(log[SUP1.59]n) copies per variable. In both cases the access time is close to the natural O(√n) lower bound imposed by the network diameter. A key feature of the scheme is that it can be made fully constructive when m is not too large, thus providing in this case the first efficient, constructive, deterministic scheme in the literature for bounded-degree processor networks. For larger memory sizes, the scheme relies solely on a nonconstructive graph of weak expansion. Finally, the scheme can be efficiently ported to other architectures, as long as they exhibit certain structural properties. In the paper we discuss the porting to multidimensional meshes and to the pruned butterfly, an area-universal network which is a variant of the fat-tree. [ABSTRACT FROM AUTHOR]

In the last decade, a large number of papers was devoted to studying probabilistic properties of epidemic models on graphs. In this paper we consider a generalization of the model proposed byMachado, Mashurian, andMatzinger. TheMachado-Mashurian-Matzinger model serves as an interpretation of spread of viruses in a computer network. We assume that at each moment of time more than one node of the network can be infected. In this context we propose a more advanced model permitting jumps of several particles each time, while the number of such particles is random. We prove the optimal version of the law of large numbers for the number of infected particles in the epidemic model at hand. [ABSTRACT FROM AUTHOR]

This paper studies synchronization via pinning control on general complex dynamical networks, such as strongly connected networks, networks with a directed spanning tree, weakly connected networks, and directed forests. A criterion for ensuring network synchronization on strongly connected networks is given. It is found that the vertices with very small in-degrees should be pinned first. In addition, it is shown that the original condition with controllers can be reformulated such that it does not depend on the form of the chosen controllers, which implies that the vertices with very large out-degrees may be pinned. Then, a criterion for achieving synchronization on networks with a directed spanning tree, which can be composed of many strongly connected components, is derived. It is found that the strongly connected components with very few connections from other components should be controlled and the components with many connections from other components can achieve synchronization even without controls. Moreover, a simple but effective pinning algorithm for reaching synchronization on a general complex dynamical network is proposed. Finally, some simulation examples are given to verify the proposed pinning scheme. [ABSTRACT FROM AUTHOR]

We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting (ϵ, k)-failures: events in which an adversary deletes up to k network elements (nodes or edges), after which there are two sets of nodes A and B, each at least an ϵ fraction of the network, that are disconnected from one another. We say that a set D of nodes is an (ϵ, k)-detection set if, for any (ϵ, k)-failure of the network, some two nodes in D are no longer able to communicate; in this way, D "witnesses" any such failure. Recent results show that for any graph G, there is an (ϵ, k)-detection set of size bounded by a polynomial in k and ϵ, independent of the size of G. In this paper, we expose some relationships between bounds on detection sets and the edge-connectivity λ and node-connectivity K of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. We show that for an adversary that can delete kλ edges, there is always a detection set of size O( k/ϵ log 1/ϵ) which can be found by random sampling. Moreover, an (ϵ, λ)-detection set of minimum size (which is at most 1/ϵ ) can be computed in polynomial time. A crucial point is that these bounds are independent not just of the size of G but also of the value of λ. Extending these bounds to node failures is much more challenging. The most technically difficult result of this paper is that a random sample of O( 1/ϵ log 1/ϵ) nodes is a detection set for adversaries that can delete a number of nodes up to λ, the node-connectivity. For the case of edge-failures we use VC-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph. [ABSTRACT FROM AUTHOR]

This paper shows that the treatment of play or backlash as an input-output operator in mechanical networks leads to solutions which are unsatisfactory from a physical point of view. This contrasts with a simple behavioral definition of ideal play. With this definition, play cannot be treated in isolation as an input-output relation. As a result, methods of nonlinear feedback systems are not readily applicable to establish well-posedness of solutions of mechanical networks incorporating this play element. By means of simple network examples, this paper explores the issues involved in establishing well-posedness of mechanical networks incorporating springs, dampers, masses, and inerters together with the behavioral model of ideal play. Connections with the approach of Nordin, Galic, and Gutman are analyzed and a model implementation given. [ABSTRACT FROM AUTHOR]

In this paper, we establish a few new synchronization conditions for complex networks with nonlinear and nonidentical self-dynamics with switching directed communication graphs. In light of the recent works on distributed subgradient methods, we impose integral convexity for the nonlinear node self-dynamics in the sense that the self-dynamics of a given node is the gradient of some concave function corresponding to that node. The node couplings are assumed to be linear but with switching directed communication graphs. Several sufficient and/or necessary conditions are established for exact or approximate synchronization over the considered complex networks. These results show when and how nonlinear node self-dynamics may cooperate with the linear diffusive coupling, which eventually leads to network synchronization conditions under relaxed connectivity requirements. [ABSTRACT FROM AUTHOR]

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each node is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to ∣V (G)∣. In this paper, we consider the common properties of a wide class of interconnection networks, called restricted hypercube-like networks, from which their conditional edge-fault pancyclicity can be determined. We then apply our technical theorems to show that several multiprocessor systems, including n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, recursive circulants G(2n, 4) for odd n, n-dimensional crossed cubes, and n-dimensional twisted cubes for odd n, are all conditional (2n-5)-edge-fault pancyclic. [ABSTRACT FROM AUTHOR]

With the help of the multilevel fast multipole algorithm, integral-equation methods can be used to solve real-life electromagnetics problems both accurately and efficiently. Increasing problem dimensions, on the other hand, necessitate effective parallel preconditioners with low setup costs. In this paper, we consider sparse approximate inverses generated from the sparse near-field part of the dense coefficient matrix. In particular, we analyze pattern selection strategies that can make efficient use of the block structure of the near-field matrix, and we propose a load-balancing method to obtain high scalability during the setup. We also present some implementation details, which reduce the computational cost of the setup phase. In conclusion, for the open-surface problems that are modeled by the electric-field integral equation, we have been able to solve ill-conditioned linear systems involving millions of unknowns with moderate computational requirements. For closed-surface problems that can be modeled by the combined-field integral equation, we reduce the solution times significantly compared to the commonly used block-diagonal preconditioner. [ABSTRACT FROM AUTHOR]

The presence of a schema offers many advantages in processing, translating, querying, and storage of XML data. Basic decision problems such as equivalence, inclusion, and nonemptiness of intersection of schemas form the basic building blocks for schema optimization and integration, and algorithms for static analysis of transformations. It is thereby paramount to establish the exact complexity of these problems. Most common schema languages for XML can be adequately modeled by some kind of grammar with regular expressions at right-hand sides. In this paper, we observe that, apart from the usual regular operators of union, concatenation, and Kleene-star, schema languages also allow numerical occurrence constraints and interleaving operators. Although the expressiveness of these operators remains within the regular languages, the presence or absence of these operators has a significant impact on the complexity of the basic decision problems. We present a complete overview of the complexity of the basic decision problems for DTDs, XSDs, and Relax NG with regular expressions incorporating numerical occurrence constraints and interleaving. We also discuss chain regular expressions and the complexity of the schema simplification problem incorporating the new operators. [ABSTRACT FROM AUTHOR]

This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterized by a finite set F of nonnegative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that computing the partition function, i.e., the sum of the weights of all configurations, is FP#P-complete unless either (1) every function in F is of "product type," or (2) every function in F is "pure affine." In the remaining cases, computing the partition function is in P. [ABSTRACT FROM AUTHOR]

Many approximation algorithms have been presented in the last decades for NP-hard search problems. The focus of this paper is on cryptographic applications, where it is desirable to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms--efficient approximation algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information. For functions, Feigenbaum et al. [ACM Trans. Algorithms, 2 (2006), pp. 435-472] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to relations is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms; applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. We argue that our privacy requirement is natural and quite minimal. We show that, even under this minimal definition of privacy, for well-studied problems such as vertex cover and max exact 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similarly to Halevi et al. [in Proceedings of the 33rd ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 550-559], we define a relaxed notion of approximation algorithms that leak (a little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for max exact 3SAT that leak a little information. [ABSTRACT FROM AUTHOR]

Virtual private network design is the following NP-hard problem. We are given a communication network represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often elusive. The main contributions of this paper are as follows: (1) Using Hu's 2-commodity flow theorem, we provide a new and considerably stronger lower bound on the cost of an optimum solution. With this lower bound we reanalyze a simple routing scheme which has been described in the literature many times, and provide an improved upper bound on its approximation ratio. (2) We present a new randomized approximation algorithm. In contrast to earlier approaches from the literature, the resulting solution does not have tree structure. A combination of our new algorithm with the simple routing scheme yields an expected performance ratio of 3.79 for virtual private network design. This is a considerable improvement of the previously best known 5.55-approximation result [A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365-372]. (3) Our VPND algorithm uses a Steiner tree approximation algorithm as a subroutine. It is known that an optimum Steiner tree can be computed in polynomial time if the number of terminals is logarithmic. Replacing the approximate Steiner tree computation with an exact one whenever the number of terminals is sufficiently small, we finally reduce the approximation ratio to 3.55. To the best of our knowledge, this is the first time that a nontrivial result from exact (exponential) algorithms leads to an improved polynomial-time approximation algorithm. [ABSTRACT FROM AUTHOR]

The aim of this paper is to introduce a macroscopic fluid dynamic model dealing with the flow of information on a telecommunication network encoded in packets. Taking an intermediate time and space scale, we propose a model similar to that introduced recently for car traffic; see [G. M. Coclite, M. Garavello, and B. Piccoli, SIAM J. Math. Anal., 36 (2005), pp. 1862-1886]. For dynamics at nodes we consider two "routing algorithms" and prove existence of solutions to Cauchy problems. The main difference among the two algorithms is the possibility of redirecting packets of the second algorithm, which in turn implies stability, i.e., Lipschitz continuous dependence on initial data, not granted for solutions using the first algorithm. [ABSTRACT FROM AUTHOR]

We show that if a minimal-time solution to a fundamental distributed computation primitive, synchronizing a network path of finite-state processors, exists on the three-dimensional, undirected grid, then we can conclude the purely complexity-theoretic result P = NP. Every previous result on network synchronization for various network topologies either demonstrates the existence of fast synchronization solutions or proves that a synchronization solution cannot exist at all. To date, it is unknown whether there is a network topology for which there exists a synchronization solution but for which no minimal-time synchronization solution exists. Under the assumption that P≠= NP, this paper solves this longstanding open problem in the affirmative. [ABSTRACT FROM AUTHOR]

We study a basic buffer management problem that arises in network switches. Consider $m$ input ports, each of which is equipped with a buffer (queue) of limited capacity. Data packets arrive online and can be stored in the buffers if space permits; otherwise packet loss occurs. In each time step the switch can transmit one packet from one of the buffers to the output port. The goal is to maximize the number of transmitted packets. Simple arguments show that any work-conserving algorithm, which serves any nonempty buffer, is 2-competitive. Azar and Richter recently presented a randomized online algorithm and gave lower bounds for deterministic and randomized strategies. In practice, greedy algorithms are very important because they are fast, use little extra memory, and reduce packet loss by always serving a longest queue. In this paper we first settle the competitive performance of the entire family of greedy strategies. We prove that greedy algorithms are not better than 2-competitive no matter how ties are broken. Our lower bound proof uses a new recursive construction for building adversarial buffer configurations that may be of independent interest. We also give improved lower bounds for deterministic and randomized online algorithms. In this paper we present the first deterministic online algorithm that is better than 2-competitive. We develop a modified greedy algorithm, called semigreedy, and prove that it achieves a competitive ratio of $17/9 \approx 1.89$. The new algorithm is simple, fast, and uses little extra memory. Only when the risk of packet loss is low does it not serve the longest queue. Additionally we study scenarios when an online algorithm is granted additional resources. We consider resource augmentation with respect to memory and speed; i.e., an online algorithm may be given larger buffers or higher transmission rates. We analyze greedy and other online strategies. [ABSTRACT FROM AUTHOR]

A Steiner quadruple system of order v, denoted by SQS(v), is a pair $(X,{\cal B}),$ where X is a v-set of points and ${\cal B}$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in exactly one block of ${\cal B}$. An SQS(v) is resolvable if its block set can be partitioned into parallel classes. In 1987, Hartman showed that the necessary condition $v\equiv 4$ or $8\ (\rm {mod}\ 12)$ for the existence of a resolvable SQS(v) is sufficient with 23 possible exceptions. In this paper, we construct resolvable SQS(v)s for the 23 undecided orders. [ABSTRACT FROM AUTHOR]

In this paper, we describe an O (|V (G)|| E (G)|) algorithm for finding a nonseparating planar chain in a 4-connected graph G, which will be used to decompose an arbitrary 4-connected graph into planar chains. This work was motivated by the study of a multitree approach to reliability in distributed networks, as well as the study of nonseparating induced paths in highly connected graphs. [ABSTRACT FROM AUTHOR]

We study directed network design problems with orientation constraints. An orientation constraint on a pair of nodes u and v states that a feasible solution may include at most one of the arcs (u, v) and (v, u). Such constraints arise naturally in many network design problems, since link or edge resources such as fiber can be used to support traffic in one of two possible directions only. Our first result is that the directed network design problem with orientation constraints can be solved in polynomial time in the case where the requirement function $f$ is positively intersecting supermodular. (The case where there are no orientation constraints follows from the work of Frank [Acta Sci. Math. (Szeged), 41 (1979), pp. 63--76].) The second main result of the paper is a 4-approximation algorithm for the minimum cost strongly edge-connected subgraph problem with orientation constraints. Our algorithm shows that the problem of enforcing orientation constraints can be reduced to the minimum cost $2$-edge-connected subgraph problem on undirected graphs. Finally, we study the problem for general crossing supermodular functions and show the following bicriteria approximation result. Let k denote the maximum requirement of any set under the given requirement function f. We give a 2k-approximation algorithm to construct a solution that satisfies a slightly weaker requirement function, namely, f'(S)=max{f (S)-1,0}. [ABSTRACT FROM AUTHOR]

Chung and Ross [SIAM J. Comput., 20 (1991), pp. 726,736] conjectured that the minimum number m(n, r) of middle-stage switches for the symmetric 3-stage Clos network C(n,m(n, r), r) to be rearrangeable in the multirate environment is at most 2n − 1. This problem is equivalent to a generalized version of the bipartite graph edge-coloring problem. The best bounds known so far on this function m(n, r) are 11n/9 ≤ m(n, r) ≤ 41n/16+O(1), for n, r ≥ 2, derived by Du et al. [SIAM J. Comput., 28 (1999), pp. 464,471]. In this paper, we make several contributions. First, we give evidence to show that even a stronger result might hold. In particular, we give a coloring algorithm to show that m(n, r) le; ⌈(r + 1)n/2⌉, which implies m(n, 2) le; ⌈3n/2⌉--stronger than the conjectured value of 2n − 1. Second, we derive that m(2, r) = 3 by an elegant argument. Last, we improve both the best upper and lower bounds given above: ⌈5n/4⌉ le; m(n, r) le; 2n−1+⌈(r−1)/2⌉, where the upper bound is an improvement over 41n/16 when r is relatively small compared to n.We also conjecture that m(n, r) ≤ ⌈2n(1 − 1/2r)⌉. [ABSTRACT FROM AUTHOR]

Rearrangeable networks can realize each and every permutation in one pass through the network. Shuffle-exchange networks provide an efficient interconnection scheme for implementing various types of parallel processes. Whether (2n - 1)-stage shuffle-exchange networks with N = 2[sup n] inputs/outputs are rearrangeable has remained an open question for approximately three decades. This question has been answered affirmatively in this paper. An important corollary of the main result is the proof that two passes through an Omega network are sufficient and necessary to implement any permutation. In obtaining the main results of this paper, frames that look like grids with horizontal links of different lengths are shown to be remarkable tools for identifying and characterizing the binary matrix representations of permutations. [ABSTRACT FROM AUTHOR]

In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone log n model by a factor of O(log n&frac;log log k). No approximation algorithms were known for the general model considered in this paper. [ABSTRACT FROM AUTHOR]

Replicated services accessed via quorums enable each access to be performed at only a subset (quorum) of the servers and achieve consistency across accesses by requiring any two quorums to intersect. Recently, b-masking quorum systems, whose intersections contain at least 2b+1 servers, have been proposed to construct replicated services tolerant of b-arbitrary (Byzantine) server failures. In this paper we consider a hybrid fault model allowing benign failures in addition to the Byzantine ones. We present four novel constructions for b-masking quorum systems in this model, each of which has optimal load (the probability of access of the busiest server) or optimal availability (probability of some quorum surviving failures). To show optimality we also prove lower bounds on the load and availability of any b-masking quorum system in this model. [ABSTRACT FROM AUTHOR]

We study virtual path layouts in a very popular type of fast interconnection networks, namely asynchronous transfer mode (ATM) networks. One of the main problems in such networks is to construct path layouts that minimize the hop-number (i.e., the number of virtual paths between any two nodes) as a function of the edge congestion c (i.e., the number of virtual paths going through a link). In this paper we construct for any n vertex network H and any c a virtual path layout with hop-number O(diam(H)logΔ/log c), where diam(H) is the diameter of the network H and Δ is its maximum degree. Involving a general lower bound from [E. Kranakis, D. Krizanc, and A. Pelc, Seventh IEEE Symposium on Parallel and Distributed Processing, IEEE Computer Society, 1995, pp. 662-668], we see that these hop-numbers are optimal for bounded degree networks with the diameter O(log n) for any congestion c. In the case of unbounded degree networks (with the diameter O(log n)) these hop-numbers are optimal for any c ≥ Δ For instance, this gives optimal hop-numbers for hypercube related networks. Moreover, we improve known results for paths and meshes and prove optimal hop-numbers for hypercubes. [ABSTRACT FROM AUTHOR]

We study networks that can sort n items even when a large number of the comparators in the network are faulty. We restrict our attention to networks that consist of registers, comparators, and replicators. (Replicators are used to copy an item from one register to another, and they are assumed to be fault free.) We consider the scenario of both random and worst-case comparator faults, and we follow the general model of destructive comparator failure proposed by Assaf and Upfal [Proc. 31st IEEE Symposium on Foundations of Computer Science, St. Louis, MO, 1990, pp. 275-284] in which the two outputs of a faulty comparator can fail independently of each other. In the case of random faults, Assaf and Upfal showed how to construct a network with O(n log[sup2]n) comparators that (with high probability) can sort n items even if a constant fraction of the comparators are faulty. Whether the bound on the number of comparators can be improved (to, say, O(nlog n)) for sorting (or merging) has remained an interesting open question. We resolve this question in this paper by proving that any n-item sorting or merging network which can tolerate a constant fraction of random failures has ω(n log[sup2] n) comparators. In the case of worst-case faults, we show that ω(kn log n) comparators are necessary to construct a sorting or merging network that can tolerate up to k worst-case faults. We also show that this bound is tight for k = O(log n). The lower bound is particularly significant since it formally proves that the cost of being tolerant to worst-case failures is very high. Both the lower bound for random faults and the lower bound for worst-case faults are the first nontrivial lower bounds on the size of a fault-tolerant sorting or merging network. Key words: merging, sorting; circuits; comparator networks; fault-tolerance; lower bounds; probabilistic analysis of algorithms [ABSTRACT FROM AUTHOR]

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(δ/α) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d[sup2] log n)/α), where δ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and α is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion α and for any value δ, there exists an initial distribution of tokens with imbalance δ for which the time to reduce the imbalance to even δ/2 is at least ω(&delta/α). The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains ω((d[sup2] log n)/α). Furthermore, we show that upon reaching a state with a global imbalance of O((d[sup2] log n)/α), the time for this algorithm to locally balance the network can be as large as δ(n[sup½]). We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step. Key words: load balancing; distributed network algorithms [ABSTRACT FROM AUTHOR]

In many applications involving incompressible fluid flow, the Stokes system plays an important role. Complex flow problems may require extremely fine resolutions, easily resulting in saddle-point problems with more than a trillion (1012) unknowns. Even on the most advanced supercomputers, the fast solution of such systems of equations is a highly nontrivial and challenging task. In this work we consider a realization of an iterative saddle-point solver which is based mathematically on the Schur-complement formulation of the pressure and algorithmically on the abstract concept of hierarchical hybrid grids. The design of our fast multigrid solver is guided by an innovative performance analysis for the computational kernels in combination with a quantification of the communication overhead. Excellent node performance and good scalability to almost a million parallel threads are demonstrated on different characteristic types of modern supercomputers. [ABSTRACT FROM AUTHOR]

We present the first constant approximation to the single sink buy-at-bulk network design problem, where we have to design a network by buying pipes of different costs and capacities per unit length to route demands at a set of sources to a single sink. The distances in the underlying network form a metric. This result improves the previous bound of O(log ∣R∣), where R is the set of sources. We also present a better constant approximation to the related Access Network Design problem. Our algorithms are randomized and combinatorial. As a subroutine in our algorithm, we use an interesting variant of facility location with lower bounds on the amount of demand an open facility needs to serve. We call this variant load balanced facility location and present a constant factor approximation for it, while relaxing the lower bounds by a constant factor. [ABSTRACT FROM AUTHOR]

We study the issue of convergence of user rates and resource prices under a family of rate control schemes called dual algorithms with arbitrary communication delays. We first consider a case where a single resource is shared by many users. Then we study a general network shared by heterogeneous users and derive sufficient conditions for convergence. We show that in the case of a single user utilizing a single resource, our condition is also necessary. Using our results we derive a sufficient condition for convergence with a family of popular utility and resource price functions. We present numerical examples to validate our analysis. [ABSTRACT FROM AUTHOR]

Link reversal algorithms provide a simple mechanism for routing in communication networks whose topology is frequently changing, such as in mobile ad hoc networks. A link reversal algorithm routes by imposing a direction on each network link such that the resulting graph is a destination oriented DAG. Whenever a node loses routes to the destination, it reacts by reversing some (or all) of its incident links. Link reversal algorithms have been studied experimentally and have been used in practical routing algorithms, including TORA [V. D. Park and M. S. Corson, A highly adaptive distributed routing algorithm for mobile wireless networks, in Proc. INFOCOM, IEEE, Los Alamitos, CA, 1997, pp. 1405--1413]. This paper presents the first formal performance analysis of link reversal algorithms. We study these algorithms in terms of work (number of node reversals) and the time needed until the network stabilizes to a state in which all the routes are reestablished. We focus on the full reversal algorithm and the partial reversal algorithm, both due to Gafni and Bertsekas [IEEE Trans. Comm.}, 29 (1981), pp. 11--18]; the first algorithm is simpler, while the latter has been found to be more efficient for typical cases. Our results are as follows: The full reversal algorithm requires O (n2) work and time, where n is the number of nodes that have lost routes to the destination. This bound is tight in the worst case. The partial reversal algorithm requires O (n $\cdot$ a* + n2) work and time, where a* is a nonnegative integral function of the initial state of the network. Further, for every nonnegative integer $\alpha$, there exists a network and an initial state with a*=$\alpha$, and with n nodes that have lost their paths to the destination, such that the partial reversal algorithm requires $\Omega(n\cdot {a^*} + n^2)$ work and time. There is an inherent lower bound on the worst-case performance of link reversal algorithms. There exist networks such that for every deterministic link reversal algorithm, there are initial states that require $\Omega(n^2)$ work and time to stabilize. Therefore, surprisingly, the full reversal algorithm is asymptotically optimal in the worst case, while the partial reversal algorithm is not, since a* can be arbitrarily larger than n. [ABSTRACT FROM AUTHOR]

Presents information on a study which examined the synchronization dynamics of connected networks of elliptic bursters. Bifurcations associated with bursting; Rhythmic processes associated with bursters; Synchronization of elliptic bursters.

We investigate a conjecture stated by Coffman, Flatto, and Wright within the context of a stochastic machine minimization problem with a hard deadline. We prove that the conjecture is true. [ABSTRACT FROM AUTHOR]

In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. For example, given any "dataflow" type of algorithm that runs in T steps on an n-node ring with unit link delays, we show how to run the algorithm in O(T) steps on any n-node bounded-degree connected network with average link delay O(1). This is a significant improvement over prior approaches to latency hiding, which require slowdowns proportional to the maximum link delay. In the case when the network has average link delay dave, our simulation runs in O(√daveT) steps using n/√dave processors, thereby preserving efficiency. We also show how to efficiently simulate an n × n array with unit link delays using slowdown Õ (d&frac23ave) on a two-dimensional array with average link delay dave. Last, we present results for the case in which large local databases are involved in the computation. [ABSTRACT FROM AUTHOR]

Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. In particular, we study trade-offs between computation overhead (load imbalance) and communication overhead (message congestion). We give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies. [ABSTRACT FROM AUTHOR]

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is #P-complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and 1/ϵ an estimate for the failure probability that is accurate to within a relative error of 1 ± ϵ with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described. [ABSTRACT FROM AUTHOR]

We describe an O(min(m, n3/2)m½)-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov and Even and Tarjan when m = ω(n3/2), and upon a randomized bound of Karger when v = Ω(n7/4/m½l). [ABSTRACT FROM AUTHOR]

We consider a class of zero-sum search games in which a Searcher seeks to minimize the expected time to find several objects hidden by a Hider. We begin by analyzing a game in which the Searcher wishes to find k balls hidden among n > k boxes. There is a known cost of searching each box, and the Searcher seeks to minimize the total expected cost of finding all the objects in the worst case. We show that it is optimal for the Searcher to begin by searching a k-subset H of boxes with probability v(H), which is proportional to the product of the search costs of the boxes in H. The Searcher should then search the n - k remaining boxes in a random order. A worst-case Hider distribution is the distribution. We distinguish between the case of a smart Searcher who can change his search plan as he goes along and a normal Searcher who has to set out his plan from the beginning. We show that a smart Searcher has no advantage. We then show how the game can be formulated in terms of a more general network search game, and we give upper and lower bounds for the value of the game on an arbitrary network. For 2-arc connected networks (networks that cannot be disconnected by the removal of fewer than two arcs), we solve the game for a smart Searcher and give an upper bound on the value for a normal Searcher. This bound is tight if the network is a circle. [ABSTRACT FROM AUTHOR]

New stability results are presented for Kelly's algorithm for network traffic control. These are applicable to a broad class of algorithms including most of those previously discussed in the literature. Three types of results are derived: an asymptotic stability result for networks with external disturbances but without time delays, an asymptotic stability result for a class of algorithms with a linear cost with both external disturbances and time delays, and a gain stability result for more general algorithms with both disturbances and time delays. The time-delay results are obtained using a gap metric approach. [ABSTRACT FROM AUTHOR]

The goal of this work is to show that if a minimal-time solution exists for a fundamental computation primitive, synchronizing networks of finite-state processors (formally known as the firing squad synchronization problems for directed and undirected networks), then there must exist "extraordinarily fast" algorithms for exactly solving the diameter problem in the standard RAM model of computation. These results can therefore be interpreted either as evidence that such minimal-time solutions for synchronization do not exist or as a potentially major algorithmic leap forward in the study of the diameter problem. We conjecture that the former is true. These results essentially complete the program outlined in [K. Kobayashi, Theoret. Comput. Sci., 259 (2001), pp. 129-143] to show that there exist a wide range of natural topologies for which it seems highly unlikely that there exist minimal-time solutions. [ABSTRACT FROM AUTHOR]

Existence, uniqueness, and approximations of smooth solutions to team optimization problems with stochastic information structure are investigated. Suboptimal strategies made up of linear combinations of basis functions containing adjustable parameters are considered. Estimates of their accuracies are derived by combining properties of the unknown optimal strategies with tools from nonlinear approximation theory. The estimates are obtained for basis functions corresponding to sinusoids with variable frequencies and phases, Gaussians with variable centers and widths, and sigmoidal ridge functions. The theoretical results are applied to a problem of optimal production in a multidivisional firm, for which numerical simulations are presented. [ABSTRACT FROM AUTHOR]

We study the price of selfish routing in noncooperative networks like the Internet. In particular, we investigate the price of selfish routing using the price of anarchy (a.k.a. the coordination ratio) and other (e.g., bicriteria) measures in the recently introduced game theoretic parallel links network model of Koutsoupias and Papadimitriou. We generalize this model toward general, monotone families of cost functions and cost functions from queueing theory. A summary of our main results for general, monotone cost functions is as follows: 1. We give an exact characterization of all cost functions having a bounded/unbounded price of anarchy. For example, the price of anarchy for cost functions describing the expected delay in queueing systems is unbounded. 2. We show that an unbounded price of anarchy implies an extremely high performance degradation under bicriteria measures. In fact, the price of selfish routing can be as high as a bandwidth degradation by a factor that is linear in the network size. 3. We separate the game theoretic (integral) allocation model from the (fractional) flow model by demonstrating that even a very small or negligible amount of integrality can lead to a dramatic performance degradation. 4. We unify recent results on selfish routing under different objectives by showing that an unbounded price of anarchy under the min-max objective implies an unbounded price of anarchy under the average cost objective and vice versa. Our special focus lies on cost functions describing the behavior of Web servers that can open only a limited number of Transmission Control Protocol (TCP) connections. In particular, we compare the performance of queueing systems that serve all incoming requests with servers that reject requests in case of overload. Our analysis indicates that all queueing systems without rejection cannot give any reasonable guarantee on the expected delay of requests under selfish routing even when the injected load is far away from the capacity of the system. In contrast, Web server farms that are allowed to reject requests can guarantee a high quality of service for every individual request stream even under relatively high injection rates. [ABSTRACT FROM AUTHOR]

Buy-at-bulk network design problems arise in settings where the costs for purchasing or installing equipment exhibit economies of scale. The objective is to build a network of cheapest cost to support a given multicommodity flow demand between node pairs. We present approximation algorithms for buy-at-bulk network design problems with costs on both edges and nodes of an undirected graph. Our main result is the first poly-logarithmic approximation ratio for the non-uniform problem that allows different cost functions on each edge and node; the ratio we achieve is O(log4 h), where h is the number of demand pairs. In addition we present an O(log h) approximation for the single sink problem. Poly-logarithmic ratios for some related problems are also obtained. Our algorithm for the multicommodity problem is obtained via a reduction to the single source problem using the notion of junction trees. We believe that this presents a simple yet useful general technique for network design problems. [ABSTRACT FROM AUTHOR]

We present an algorithm with runtime O(k2kn³m) for the following NP-complete problem [M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979, problem GT35]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question [H. Kaplan, R. Shamir, and R. E. Tarjan, SIAM J. Comput., 28 (1999), pp. 1906-1922; R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999; M. Serna and D. Thilikos, Bull. Eur. Assoc. Theory Comput. Sci. EATCS, 86 (2005), pp. 41-65; G. Gutin, S. Szeider, and A. Yeo, in Proceedings IWPEC 2006, Lecture Notes in Comput. Sci. 4169, Springer-Verlag, Berlin, 2006, pp. 60-71], first posed by Kaplan, Shamir, and Tarjan, of whether this problem was fixed parameter tractable. The problem has applications in profile minimization for sparse matrix computations [J. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; R. E. Tarjan, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, 1976, pp. 3-22], and our results show tractability for the case of a small number k of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph and combines this with a greedy algorithm when graphs of a certain structure are reached by the search. [ABSTRACT FROM AUTHOR]

We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: (a) the Blum-Shub-Smale model of computation over the reals; and (b) a problem we call the "generic task of numerical computation," which captures an aspect of doing numerical computation in floating point, similar to the "long exponent model" that has been studied in the numerical computing community. We show that both of these approaches hinge on the question of understanding the complexity of the following problem, which we call PosSLP: Given a division-free straight-line program producing an integer N, decide whether N >0. In the Blum-Shub-Smale model, polynomial-time computation over the reals (on discrete inputs) is polynomial-time equivalent to PosSLP when there are only algebraic constants. We conjecture that using transcendental constants provides no additional power, beyond nonuniform reductions to PosSLP, and we present some preliminary results supporting this conjecture. The generic task of numerical computation is also polynomial-time equivalent to PosSLP. We prove that PosSLP lies in the counting hierarchy. Combining this with work of Tiwari, we obtain that the Euclidean traveling salesman problem lies in the counting hierarchy--the previous best upper bound for this important problem (in terms of classical complexity classes) being PSPACE. In the course of developing the context for our results on arithmetic circuits, we present some new observations on the complexity of the arithmetic circuit identity testing (ACIT) problem. In particular, we show that if n! is not ultimately easy, then ACIT has subexponential complexity. [ABSTRACT FROM AUTHOR]

We provide a suite of impossibility results and lower bounds for the required number of processes and rounds for synchronous consensus under transient link failures. Our results show that consensus can be solved even in the presence of O(n²) moving omission and/or arbitrary link failures per round, provided that both the number of affected outgoing and incoming links of every process is bounded. Providing a step further toward the weakest conditions under which consensus is solvable, our findings are applicable to a variety of dynamic phenomena such as transient communication failures and end-to-end delay variations. We also prove that our model surpasses alternative link failure modeling approaches in terms of assumption coverage. [ABSTRACT FROM AUTHOR]

We put forward a new type of computationally sound proof system called universal arguments. Universal arguments are related but different from both CS proofs (as defined by Micali [SIAM J. Comput., 37 (2000), pp. 1253-1298]) and arguments (as defined by Brassard, Chaum, and Crépeau [J. Comput. System Sci., 37 (1988), pp. 156-189]. In particular, we adopt the instance-based prover-efficiency paradigm of CS proofs but follow the computational-soundness condition of argument systems (i.e., we consider only cheating strategies that are implementable by polynomial-size circuits). We show that universal arguments can be constructed based on standard intractability assumptions that refer to polynomial-size circuits (rather than based on assumptions that refer to subexponential-size circuits as used in the construction of CS proofs). Furthermore, these protocols have a constant number of rounds and are of the public-coin type. As an application of these universal arguments, we weaken the intractability assumptions used in the non-black-box zero-knowledge arguments of Barak [in Proceedings of the 42nd IEEE Symposiun on Foundations of Computer Science, 2001]. Specifically, we only utilize intractability assumptions that refer to polynomial-size circuits (rather than assumptions that refer to circuits of some "nice" superpolynomial size). [ABSTRACT FROM AUTHOR]

Motivated by the connection between graph decompositions and traffic grooming in optical networks, we continue the investigation of the existence problem for (K5 \ e)-designs of order n. It is proved that the necessary conditions for the existence of such designs are also sufficient with 3 definite exceptions (n = 9, 10, 18) and 12 possible exceptions with n = 234 being the largest. This gives a near solution for the long standing problem posed by Bermond et al. in [Ars Combin., 10 (1980), pp. 211-254]. As a consequence, we also give an optimal grooming on n nodes with C = 9 when such a (K5 \e)-design of order n exists. [ABSTRACT FROM AUTHOR]

Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Traditionally, flows over time are solved in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static flows, its main and often fatal drawback is the enormous size of the time-expanded network. We present several approaches for coping with this difficulty. First, inspired by the work of Ford and Fulkerson on maximal s-t-flows over time (or ‘maximal dynamic s-t-flows’), we show that static length-bounded flows lead to provably good multicommodity flows over time. Second, we investigate ‘condensed’ time-expanded networks which rely on a rougher discretization of time. We prove that a solution of arbitrary precision can be computed in polynomial time through an appropriate discretization leading to a condensed time-expanded network of polynomial size. In particular, our approach yields fully polynomial-time approximation schemes for the NP-hard quickest min-cost and multicommodity flow problems. For single commodity problems, we show that storage of flow at intermediate nodes is unnecessary, and our approximation schemes do not use any. [ABSTRACT FROM AUTHOR]

We analyze a second order, linear, elliptic PDE with mixed boundary conditions. This problem arose as a limiting case of a Markov-modulated queueing model for data handling switches in communications networks. We use singular perturbation methods to analyze the problem. In particular we use the ray method to solve the PDE in the limit where convection dominates diffusion. We show that there are both interior and boundary caustics, as well as a cusp point where two caustics meet, an internal layer, boundary layers, and a corner layer. Our analysis leads to approximate formulas for the queue length (or buffer content) distribution at the switch. [ABSTRACT FROM AUTHOR]

We propose a framework to analyze and compare wavelength division multiplexed (WDM) switching networks qualitatively and quantitatively. The framework not only helps analyze and compare the complexity of WDM switching networks but also explains interesting properties of different designs. Then several important problems arising from this idea are addressed, and complexity bounds are derived. We also give several applications of the proposed model, including explicit constructions of nonblocking WDM switching fabrics. [ABSTRACT FROM AUTHOR]