In this paper, we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single...
详细信息
In this paper, we investigate the problem of determining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations;in fact, most flows in the Internet are confluent since Internet routing is destination based. We consider the single-commodity confluent flow problem, in which we are given an n-node directed network G, a sink t and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform;the algorithm finds a confluent flow with edge (and node) congestion O (C(2)log(3)n), where C is the node congestion of a splittable flow with minimum node congestion;here the node congestion of a flow is the maximum, over all nodes other than t, of the congestion at a node. This implies an (O) over tilde(root n) approximation algorithm for the problem with uniform supplies. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest. For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 3/2. We also establish a lower bound on the gap between confluent and splittable flows, and consider multi-commodity and fractional versions of confluent flow problems. (C) 2005 Elsevier Inc. All rights reserved.
The paper presents a randomised algorithm which evaluates the partition function of an arbitrary ferromagnetic Ising system to any specified degree of accuracy. The running time of the algorithm increases only polynom...
详细信息
The paper presents a randomised algorithm which evaluates the partition function of an arbitrary ferromagnetic Ising system to any specified degree of accuracy. The running time of the algorithm increases only polynomially with the size of the system (i.e., the number of sites) and a parameter which controls the accuracy of the result. Further approximation algorithms are presented for the mean energy and the mean magnetic moment of ferromagnetic Ising systems. The algorithms are based on Monte Carlo simulation of a suitably defined ergodic Markov chain. The states of the chain are not, as is customary, Ising spin configurations, but spanning subgraphs of the interaction graph of the system. It is shown that the expectations of simple operators on these configurations give numerical information about the partition function and related quantities. The performance guarantees for the algorithms are rigorously derived and rest on the fact that the Markov chain in question is rapidly mixing, i.e., converges to its equilibrium distribution in a polynomial number of steps. This is apparently the first time that rapid mixing has been demonstrated at all temperatures for a Markov chain related to the Ising model.
In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting ...
详细信息
In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537550]. In this paper we consider the low-frequency range, when f = O(log n), and obtain deterministic algorithms with a (1 + \epsilon )f-approximation ratio and the following guarantees on the update time. (1) O ((f /\epsilon ) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1 + \epsilon )f-approximation algorithm with O((f2/\epsilon ) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon3 + (f/\epsilon2) \cdot log C\bigr) amortized update time: This result improves the above update time bound for most values off in the low-frequency range, i.e., f = o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon )-approximate minimum vertex cover in O(1/\epsilon2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon3) \cdot log2(Cn)) worst-ca
Given a range space (X, R), where R subset of 2(X), the hitting set problem is to find a smallest-cardinality subset H subset of X that intersects each set in R. We present near-linear-time approximation algorithms fo...
详细信息
Given a range space (X, R), where R subset of 2(X), the hitting set problem is to find a smallest-cardinality subset H subset of X that intersects each set in R. We present near-linear-time approximation algorithms for the hitting set problem in the following geometric settings: (i) R is a set of planar regions with small union complexity. (ii) R is a set of axis-parallel d-dimensional boxes in R-d. In both cases X is either the entire R-d, or a finite set of points in Rd. The approximation factors yielded by the algorithm are small;they are either the same as, or within very small factors off the best factors known to be computable in polynomial time.
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to...
详细信息
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to replenish energy via replacing batteries. An effective approach for energy conservation is scheduling sleep intervals for some sensors, while the remaining sensors stay active providing continuous service. In this paper we consider the problem of selecting a set of active sensors of minimum cardinality so that sensing coverage and network connectivity are maintained. We show that the greedy algorithm that provides complete coverage has an approximation factor no better than Omega(log n), where n is the number of sensor nodes. Then we present algorithms that provide approximate coverage while the number of nodes selected is a constant factor far from the optimal solution. Finally, we show how to connect a set of sensors that already provides coverage.
In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi-Organization Scheduling Problem (MOSP). Each organization provides both reso...
详细信息
In this paper we consider the problem of scheduling on computing platforms composed of several independent organizations, known as the Multi-Organization Scheduling Problem (MOSP). Each organization provides both resources and jobs and follows its own objectives. We are interested in the best way to minimize the makespan on the entire platform when the organizations behave in a selfish way. We study the complexity of the MOSP problem with two different local objectives-makespan and average completion time-and show that MOSP is strongly NP-Hard in both cases. We formally define a selfishness notion, by means of restrictions on the schedules. We prove that selfish behavior imposes a lower bound of 2 on the approximation ratio for the global makespan. We present various approximation algorithms of ratio 2 which validate selfishness restrictions. These algorithms are experimentally evaluated through simulation, exhibiting good average performances and presenting good fairness to organizations' local objectives. Copyright (C) 2011 John Wiley & Sons, Ltd.
The classical stochastic approximation methods are shown to yield algorithms to solve several formulations of the PAC learning problem defined on the domain [0,1](d). Under some smoothness conditions on the probabilit...
详细信息
The classical stochastic approximation methods are shown to yield algorithms to solve several formulations of the PAC learning problem defined on the domain [0,1](d). Under some smoothness conditions on the probability measure functions, simple algorithms to solve some PAC learning problems are proposed based on networks of nonpolynomial units (e.g. artificial neural networks). Conditions on the sizes of the samples required to ensure the error bounds are derived using martingale inequalities.
Our work is motivated by the need to manage data items on a collection of storage devices to handle dynamically changing demand. As demand for data items changes, for performance reasons, the system needs to automatic...
详细信息
Our work is motivated by the need to manage data items on a collection of storage devices to handle dynamically changing demand. As demand for data items changes, for performance reasons, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in Khuller, Kim and Wan (algorithms for data migration with cloning. SIAM J. Comput. 33(2):448-461, 2004). In this paper we develop an improved approximation algorithm that gives a bound of 6.5+o(1) using new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5 using external disks. We also consider the full duplex communication model and develop an improved bound of 4+o(1) for this model, with no external disks.
Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices sequentially until it...
详细信息
Suppose a target is hidden in one of the vertices of an edge-weighted graph according to a known probability distribution. Starting from a fixed root node, an expanding search visits the vertices sequentially until it finds the target, where the next vertex can be reached from any of the previously visited vertices. That is, the time to reach the next vertex equals the shortest-path distance from the set of all previously visited vertices. The expanding search problem then asks for a sequence of the nodes, so as to minimize the expected time to finding the target. This problem has numerous applications, such as searching for hidden explosives, mining coal, and disaster relief. In this paper, we develop exact algorithms and heuristics, including a branch-and-cut procedure, a greedy algorithm with a constant-factor approximation guarantee, and a local search procedure based on a spanning-tree neighborhood. Computational experiments show that our branch-and-cut procedure outperforms existing methods for instances with nonuniform probability distributions and that both our heuristics compute near-optimal solutions with little computational effort. Summary of Contribution: This paper studies new algorithms for the expanding search problem, which asks to search a graph for a target hidden in one of the nodes according to a known probability distribution. This problem has applications such as searching for hidden explosives, mining coal, and disaster relief. We propose several new algorithms, including a branch-and-cut procedure, a greedy algorithm, and a local search procedure;and we analyze their performance both experimentally and theoretically. Our analysis shows that the algorithms improve on the performance of existing methods and establishes the first constant-factor approximation guarantee for this problem.
We present an O(n(3))-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 61/81, where n is the number of vertices in the input complete edge-weighted (u...
详细信息
We present an O(n(3))-time approximation algorithm for the maximum traveling salesman problem whose approximation ratio is asymptotically 61/81, where n is the number of vertices in the input complete edge-weighted (undirected) graph. We also present an O(n(3))-time approximation algorithm for the metric case of the problem whose approximation ratio is asymptotically 17/20. Both algorithms improve on the previous bests. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论