The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex tree T = (V, E) and an additional set L...
详细信息
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex tree T = (V, E) and an additional set L subset of ((V)(2)) of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T boolean OR F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log 2 n)-competitive algorithm and showed an Omega (log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O (log n)-competitive algorithm for online WTAP, which is tight up to constant factors.
This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1-7:27, 2015) showed a fundamental lower bound of Ome...
详细信息
This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1-7:27, 2015) showed a fundamental lower bound of Omega(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability;this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134-143, 2015) established a tight bound of (Theta) over tilde(root n) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of (Theta) over tilde (n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 - n(-c), for some fixed positive constant c) succeeds and uses O(n log(3) n) messages and runs in O(1) rounds;this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs O(n) messages (even when n is known), regardless of the number of rounds. We also present an O(n log n) message deterministic algorithm that takes O(log n) rounds (but needs knowledge of n);we show that this message complexity is tight for deterministic algorithms. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-a-vis the graph diameter.
We consider the Hitchcock transportation problem on n supply points and k demand points when n is much greater than k. The problem can be solved in O(kn(2) log n + n(2) log(2) n) time if an efficient minimum-cost flow...
详细信息
We consider the Hitchcock transportation problem on n supply points and k demand points when n is much greater than k. The problem can be solved in O(kn(2) log n + n(2) log(2) n) time if an efficient minimum-cost flow algorithm is directly applied. Applying a geometric method named splitter finding and a randomization technique. we can improve the time complexity when the ratio c of the maximum supply to the minimum supply is sufficiently small. The expected running time of our randomized algorithm is O(kn log cn/log(n/k(4) log(2) k)) if n > k(4) log(2) k, and O(k(5) log(2) n log cn) if n less than or equal to k(4) log(2) k. If n = Omega(k(4+epsilon) (epsilon > 0) and c = poly(n), the problem is solved in O(kn) time, which is optimal.
In this paper we study the sorting performance of a 128-processor CRAY T3D and discuss the efficient use of the toroidal network connecting the processors. The problems we consider range from that of sorting one word ...
详细信息
In this paper we study the sorting performance of a 128-processor CRAY T3D and discuss the efficient use of the toroidal network connecting the processors. The problems we consider range from that of sorting one word per processor to sorting the entire memory of the machine, and we give efficient algorithms for each case. In addition, we give both algorithms that make assumptions about the distribution of the data and those that make no assumptions. The clear winner, if data can be assumed to be uniformly distributed, is a method that we call a hash-and-chain sort. The time for this algorithm to sort one million words per processor over 64 processors is less than two seconds, which compares favorably to about four seconds using a 4-processor CRAY C90 and about 17 seconds using a 64-processor Thinking Machines CM-5.
In multi-hop radio networks, such as wireless ad-hoc networks and wireless sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid int...
详细信息
In multi-hop radio networks, such as wireless ad-hoc networks and wireless sensor networks, nodes employ a MAC (Medium Access Control) protocol such as TDMA to coordinate accesses to the shared medium and to avoid interference of close-by transmissions. These protocols can be implemented using standard node coloring. The (Delta + 1)-coloring problem is to color all nodes in as few timeslots as possible using at most Delta + 1 colors such that any two nodes within distance R are assigned different colors, where R is a given parameter and Delta is the maximum degree of the modeled unit disk graph using R as a scaling factor. Being one of the most fundamental problems in distributed computing, this problem is well studied and there is a long chain of algorithms prescribed for it. However, all previous works are based on abstract models, such as message passing models and graph based interference models, which limit the utility of these algorithms in practice. In this paper, for the first time, we consider the distributed (Delta + 1)-coloring problem under the more practical SINR interference model. In particular, without requiring any knowledge about the neighborhood, we propose a novel randomized (Delta + 1)-coloring algorithm with time complexity O (Delta log n + log(2) n). For the case where nodes cannot adjust their transmission power, we give an O (Delta log(2) n) randomized algorithm, which only incurs a logarithmic multiplicative factor overhead. (C) 2014 Elsevier B.V. All rights reserved.
Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known ...
详细信息
Knapsack median is a generalization of the classic k-median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation.
We consider a setup where a distributed set of sensors working cooperatively can estimate an unknown signal of interest, whereas any individual sensor cannot fulfill the task due to lack of necessary information diver...
详细信息
We consider a setup where a distributed set of sensors working cooperatively can estimate an unknown signal of interest, whereas any individual sensor cannot fulfill the task due to lack of necessary information diversity. This article deals with these kinds of estimation and tracking problems and focuses on a class of simultaneous perturbation stochastic approximation (SPSA)-based consensus algorithms for the cases when the corrupted observations of sensors are transmitted between sensors with communication noise and the communication protocol has to satisfy a prespecified cost constraints on the network topology. Sufficient conditions are introduced to guarantee the stability of estimates obtained in this way, without resorting to commonly used but stringent conventional statistical assumptions about the observation noise, such as randomness, independence, and zero mean. We derive an upper bound of the mean square error of the estimates in the problem of unknown time-varying parameters tracking under unknown-but-bounded observation errors and noisy communication channels. The result is illustrated by a practical application to the multisensor multitarget tracking problem.
We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graph...
详细信息
We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graphs (G(n),(m),((p) over right arrow)) which includes the model of [M. Karonski, E.R. Scheinerman, K.B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combinatorics, Probability and Computing journal 8 (1999), 131-159] (the "uniform" random intersection graph models) as an important special case. We also define an interesting variation of the model of random intersection graphs, similar in spirit to random regular graphs. (b) For this model we derive exact formulae for the mean and variance of the number of independent sets of size k (for any k) in the graph. (c) We then propose and analyse three algorithms for the efficient construction of large independent sets in this model. The first two are variations of the greedy technique while the third is a totally new algorithm. Our algorithms are analysed for the special case of uniform random intersection graphs. Our analyses show that these algorithms succeed in finding close to optimal independent sets for an interesting range of graph parameters. (c) 2008 Elsevier B.V. All rights reserved.
Iterative learning control (ILC) has been successfully applied to numerous batch processes over the past decades. Monotonic convergence of tracking error is a desired characteristic that attracts much attention in aca...
详细信息
Iterative learning control (ILC) has been successfully applied to numerous batch processes over the past decades. Monotonic convergence of tracking error is a desired characteristic that attracts much attention in academia. Many factors arising in industrial practice, such as strong nonlinearity and parameter uncertainty, have challenged the most existing monotonically convergent ILC approaches. This motivates the development of the nonlinear monotonically convergent ILC (NMC-ILC) in this paper. The proposed NMC-ILC is an optimization-based control strategy, in which the original nonlinear process is linearly approximated to reduce the complexity of the optimization problem accompanied. An upper bound of the tracking error is derived by considering the effects of model mismatches that consist of two components: structural mismatch induced by the linearization and parametric mismatch arising from the indetermination of process parameters. The NMC-ILC is then devised by minimizing this upper bound. Numerical experiments are conducted on an ILC-testing benchmark and the velocity control in an injection molding process.
Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fraction...
详细信息
Given an undirected graph, a minimum cut cover is a collection of cuts covering the whole set of edges and having minimum cardinality. This paper is dedicated to the fractional version of this problem where a fractional weight is computed for each cut such that, for each edge, the sum of the weights of all cuts containing it is no less than 1, while the sum of all weights is minimized. The fractional cover is computed for different graph classes among which are the weakly bipartite graphs. Efficient algorithms are described to compute lower and upper bounds with worst-case performance guarantees. A general randomized approach is also presented giving new insights into Goemans and Williamson's algorithm for the maximum cut problem. Some numerical experiments are included to assess the quality of bounds. (C) 2019 Elsevier B.V. All rights reserved.
暂无评论