检索结果-内蒙古大学图书馆

approximation algorithms for maximum cut with limited unbalance

THEORETICAL COMPUTER SCIENCE 2007年第1-3期385卷 78-87页

作者： Galbiati, Giulia Maffioli, Francesco Univ Pavia Dipartimento Informat & Sistemist I-27100 Pavia Italy Politecn Milan Dipartimento Elettron & Informaz I-20133 Milan Italy

We consider the problem of partitioning the vertices of a weighted graph into two sets of sizes that differ at most by a given threshold B, so as to maximize the weight of the crossing edges. For B equal to 0 this problem is known as Max Bisection, whereas for B equal to the number n of nodes it is the maximum cut problem. We present polynomial time randomized approximation algorithms with non trivial performance guarantees for its solution. The approximation results are obtained by extending the methodology used by Y. Ye for Max Bisection and by combining this technique with another one that uses the algorithm of Goemans and Williamson for the maximum cut problem. When B is equal to zero the approximation ratio achieved coincides with the one obtained by Y. Ye;otherwise it is always above this value and tends to the value obtained by Goemans and Williamson as B approaches the number n of nodes. (c) 2007 Elsevier B.V. All rights reserved.

关键词： randomized approximation algorithm semidefinite programming maximum cut limited unbalance cut

来源：评论

学校读者我要写书评

暂无评论

A Distributed Information Divergence Estimation over Data Streams

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2014年第2期25卷 478-487页

作者： Anceaume, Emmanuelle Busnel, Yann IRISA CNRS F-35042 Rennes France Univ Nantes LINA Dept Comp Sci F-44322 Nantes 3 France

In this paper, we consider the setting of large-scale distributed systems, in which each node needs to quickly process a huge amount of data received in the form of a stream that may have been tampered with by an adversary. In this situation, a fundamental problem is how to detect and quantify the amount of work performed by the adversary. To address this issue, we propose a novel algorithm AnKLe for estimating the Kullback-Leibler divergence of an observed stream compared with the expected one. AnKLe combines sampling techniques and information-theoretic methods. It is very efficient, both in terms of space and time complexities, and requires only a single pass over the data stream. We show that AnKLe is an (epsilon, delta)-approximation algorithm with a space complexity (O) over tilde (1/epsilon+1/epsilon(2)) bits in "most" cases, and (O) over tilde (1/epsilon+n-epsilon (1)/epsilon(2)) otherwise, where n is the number of distinct data items in a stream. Moreover, we propose a distributed version of AnKLe that requires at most O(rl(log n + 1) bits of communication between the l participating nodes, where r is number of rounds of the algorithm. Experimental results show that the estimation provided by AnKLe remains accurate even for different adversarial settings for which the quality of other methods dramatically decreases.

关键词： Data stream Kullback-Leibler divergence randomized approximation algorithm byzantine adversary performance analysis

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Online User Association in Multi-Tier Multi-Cell Mobile Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2017年第4期25卷 2361-2374页

作者： Ao, Weng Chon Psounis, Konstantinos Univ Southern Calif Dept Elect Engn & Comp Sci Los Angeles CA 90089 USA

The constantly growing wireless bandwidth demand is pushing wireless networks to multi-tier architectures consisting of a macrocell tier and a number of dense small cell deployment tiers. In such a multi-tier multi-cell environment, the classic problem of associating users to base stations becomes both more challenging and more critical to the overall network performance. Most previous analytical work is focused on designing static user-cell association algorithms, which, to achieve optimality, are periodically applied whenever there are new user arrivals, thus potentially inducing a large number of re-associations for previously arrived users. On the other hand, practical online algorithms that do not allow any such user re-association are often based on heuristics and may not have any performance guarantees. In this paper, we propose online algorithms for the multi-tier multi-cell user association problem that have provable performance guarantees, which improve previously known bounds by a sizable amount. The proposed algorithms are motivated by online combinatorial auctions, while capturing and leveraging the relative sparsity of choices in wireless networks as compared with auction setups. Our champion algorithm is a 1/2-alpha(-1) approximation algorithm, where a is the maximum number of feasible associations for a user and is, in general, small due to path loss. Our analysis considers the state-of-the-art wireless technologies, such as massive and multiuser MIMO, and practical aspects of the system such as the fact that highly mobile users have a preference to connect to larger cell tiers to keep the signaling overhead low. In addition to establishing formal performance bounds, we also conduct simulations under realistic assumptions, which establish the superiority of the proposed algorithm over existing approaches under real-world scenarios.

关键词： User association load balancing heterogeneous cellular networks multi-user MIMO massive MIMO mobility online algorithm randomized approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Distributed O(1)-approximation algorithm for the Uniform Facility Location Problem

引用

algorithmICA 2014年第3期68卷 643-670页

作者： Gehweiler, Joachim Lammersen, Christiane Sohler, Christian Univ Paderborn Heinz Nixdorf Inst D-33095 Paderborn Germany Univ Paderborn Dept Comp Sci D-33095 Paderborn Germany Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Tech Univ Dortmund Dept Comp Sci D-44221 Dortmund Germany

We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized. We present a randomized distributed algorithm that computes in expectation an -approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by message passing. We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to bits, where n is the number of input points. We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent a""a parts per thousand yen1, we obtain a randomized -approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to bits.

关键词： Facility location Distributed algorithm randomized approximation algorithm Synchronous message passing model

来源：评论

学校读者我要写书评

暂无评论

A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期385卷 101-114页

作者： Khan, Maleq Pandurangan, Gopal Kumar, V. S. Anil Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA

The main focus of this paper is the analysis of a simple randomized scheme for constructing low-weight k-connected spanning subgraphs. In this paper, we focus on the metric graph. We use the term metric graph for a complete graph with metric weights. We first show that our scheme gives a simple approximation algorithm to construct a minimum-weight k-connected spanning subgraph in a metric graph, an NP-hard problem. We show that our algorithm gives an approximation ratio of O(k log n) for a metric graph, O(k) for a random graph with nodes uniformly randomly distributed in [0, 1](2) and O(log n/k) for a complete graph k with random edge weights U(0, 1). We show that our scheme is optimal with respect to the amount of "local information" needed to compute any connected spanning subgraph. We then show that our scheme can be applied to design an efficient distributed algorithm for constructing such an approximate k-connected spanning subgraph (for any k >= 1) in a point-to-point distributed model, where the processors form a complete network. Our algorithm takes O(log n/k) time and an expected number of O(nk log n/k) messages. Our result in conjunction with a result of Korach et al. [E. Korach, S. Moran, S. Zaks, The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, SIAM Journal on Computing 16 (2) (1987) 231-236] implies that the expected message complexity of our algorithm is significantly better than the best distributed algorithm that finds an optimal k-connected subgraph. We also show that for geometric instances, our randomized scheme constructs low-degree k-connected spanning subgraphs which have O(k log n) maximum degree, with high probability. (c) 2007 Elsevier B.V. All rights reserved.

关键词： k-connected spanning subgraph minimum spanning tree randomized approximation algorithm distributed algorithm probabilistic analysis

来源：评论

学校读者我要写书评

暂无评论

Minimal Cost Server Configuration for Meeting Time-Varying Resource Demands in Cloud Centers

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2018年第11期29卷 2503-2513页

作者： Liu, Chubo Li, Kenli Li, Keqin Hunan Univ Coll Informat Sci & Engn Changsha 410082 Hunan Peoples R China Natl Supercomp Ctr Changsha 410082 Hunan Peoples R China SUNY Coll New Paltz Dept Comp Sci New Paltz NY 12561 USA

We consider the minimal cost server configuration for meeting resource demands over multiple time slots. Specifically, there are some heterogeneous servers. Each server is specified by a cost, certain amounts of several resources, and an active interval, i.e., the time interval that the server is planed to work. There are different overall demands for each type of resource over different time slots. A feasible solution is a set of servers such that at any time slot, the resources provided by the selected servers are at least their corresponding demands. Notice that, a selected server can not provide resources for the time slots out of its active interval. The total cost of the solution is the summation of the costs of all selected servers. The goal is to find a feasible solution with minimal total cost. This problem is proved to be NP-hard due to a reduction from the multidimensional knapsack problem (MKP), which is a well-known NP-hard combinational optimization problem. To solve our problem, we present a randomized approximation algorithm called partial rounding algorithm (PRA), which guarantees O(log(KT))-approximation, i.e., eta log(KT)-approximation, where K is the number of kinds of resources, T is the number of time slots, and h is a positive constant. Furthermore, to minimize h as much as possible, we propose a varied Chernoff bound and apply it in PRA. We perform extensive experiments with random inputs and a specific application input. The results show that PRA with our varied Chernoff conclusion can find solutions closing to the optimal one.

关键词： Cost minimization meeting resource demands randomized approximation algorithm server configuration varied Chernoff bound

来源：评论

学校读者我要写书评

暂无评论

Computational Experience with a SDP-Based algorithm for Maximum Cut with Limited Unbalance

引用

NETWORKS 2010年第3期55卷 247-255页

作者： Galbiati, Giulia Gualandi, Stefano Maffioli, Francesco Politecn Milan Dipartimento Elettron & Informaz I-20133 Milan Italy Univ Pavia Dipartimento Informat & Sistemist I-27100 Pavia Italy

In the Maximum Cut with Limited Unbalance problem, we want to partition the vertices of a weighted graph into two sets of sizes differing at most by a given threshold B, so that the sum of the weights of the crossing edges is maximum. This problem has been introduced in (Galbiati and Maffioli, Theor Comput Sci 385 (2007), 78-87) where polynomial time randomized approximation algorithms are proposed and their performance guarantees are analyzed in the case of non-negative integer weights. In this article, we present extensive computational experience with these algorithms on a large number of different graphs. We then extend the analysis of these algorithms to integer weights not restricted in sign, and continue the computational testing. It turns out that the approximation ratios obtained are always substantially better than those guaranteed by the theoretical analysis. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 55(3), 247-255 2010

关键词： network design randomized approximation algorithm semidefinite programming unbalanced maximum cut

来源：评论

学校读者我要写书评

暂无评论

An Efficient approximation algorithm for Online Multi-Tier Multi-Cell User Association 16

An Efficient Approximation Algorithm for Online Multi-Tier M...

引用

17th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

作者： Ao, Weng Chon Psounis, Konstantinos Univ Southern Calif Los Angeles CA 90007 USA

ISBN: (纸本)9781450341844

The ever growing wireless bandwidth demand is pushing WiFi and cellular networks to dense multi-cell deployments, as well as to multi-tier architectures consisting of macrocells and small cells. In such a multi-tier multi-cell environment, the classic problem of associating users to base stations becomes both more challenging and more critical to the overall network performance. Most previous analytical work is focused on offline/static user-cell association, where the users' arrivals and their rates are assumed to be known in advance and thus has little practical relevance. On the other hand, practical online algorithms based on heuristics are often suboptimal and may not provide any performance guarantees. In this paper, we propose an online algorithm for the multi-tier multi-cell user association problem that has a provable performance guarantee which improves previously known bounds by a sizable amount. The proposed algorithm is motivated by online combinatorial auctions, while capturing and leveraging the relative sparsity of choices in wireless networks as compared to auction setups. Specifically, it is a 1/2-a-1 approximation algorithm, where a is the maximum number of feasible associations for a user and is, in general, small due to path loss. In addition to establishing formal performance bounds, we also conduct simulations under realistic assumptions which establish the superiority of the proposed algorithm over existing approaches under real-world scenarios.

关键词： User association Load balancing Heterogeneous networks Online algorithm randomized approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Uniform Node Sampling Service Robust against Collusions of Malicious Nodes

Uniform Node Sampling Service Robust against Collusions of M...

引用

43rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

作者： Anceaume, Emmanuelle Busnel, Yann Sericola, Bruno IRISA CNRS Rennes France Univ Nantes LINA Nantes France Inria Rennes Bretagne France

ISBN: (纸本)9781479901814;9781467364713

We consider the problem of achieving uniform node sampling in large scale systems in presence of a strong adversary. We first propose an omniscient strategy that processes on the fly an unbounded and arbitrarily biased input stream made of node identifiers exchanged within the system, and outputs a stream that preserves Uniformity and Freshness properties. We show through Markov chains analysis that both properties hold despite any arbitrary bias introduced by the adversary. We then propose a knowledge-free strategy and show through extensive simulations that this strategy accurately approximates the omniscient one. We also evaluate its resilience against a strong adversary by studying two representative attacks (flooding and targeted attacks). We quantify the minimum number of identifiers that the adversary must insert in the input stream to prevent uniformity. To our knowledge, such an analysis has never been proposed before.

关键词： Data stream strong adversary uniform sampling Markov chains randomized approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Information Divergence Estimation over Data Streams

An Information Divergence Estimation over Data Streams

引用

11th IEEE International Symposium on Network Computing and Applications (NCA)

作者： Anceaume, Emmanuelle Busnel, Yann IRISA CNRS Rennes France Univ Nantes LINA F-44035 Nantes France

ISBN: (纸本)9780769547732

In this paper, we consider the setting of large scale distributed systems, in which each node needs to quickly process a huge amount of data received in the form of a stream that may have been tampered with by an adversary. In this situation, a fundamental problem is how to detect and quantify the amount of work performed by the adversary. To address this issue, we have proposed in a prior work, AnKLe, a one pass algorithm for estimating the Kullback-Leibler divergence of an observed stream compared to the expected one. Experimental evaluations have shown that the estimation provided by AnKLe is accurate for different adversarial settings for which the quality of other methods dramatically decreases. In the present paper, considering n as the number of distinct data items in a stream, we show that AnKLe is an (epsilon, delta)-approximation algorithm with a space complexity (O) over tilde (1/epsilon + 1/epsilon(2)) bits in "most" cases, and (O) over tilde (1/epsilon + n-epsilon(-1)/epsilon(2)) otherwise. To the best of our knowledge, an approximation algorithm for estimating the Kullback-Leibler divergence has never been analyzed before.

关键词： Data stream divergence randomized approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：