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

37th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Xu, Zichuan Liang, Weifa Huang, Meitian Jia, Mike Guo, Song Galis, Alex Australian Natl Univ Canberra ACT 0200 Australia UCL London WC1E 7JE England Hong Kong Polytech Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781538617915

Multicasting is a fundamental functionality of networks for many applications including online conferencing, event monitoring, video streaming, and system monitoring in data centers. To ensure multicasting reliable, secure and scalable, a service chain consisting of network functions (e.g., firewalls, Intrusion Detection Systems (IDSs), and transcoders) usually is associated with each multicast request. Such a multicast request is referred to as an NFV-enabled multicast request. In this paper we study NFV-enabled multicasting in a Software-Defined Network (SDN) with the aims to minimize the implementation cost of each NFV-enabled multicast request or maximize the network throughput for a sequence of NFV-enabled requests, subject to network resource capacity constraints. We first formulate novel NFV-enabled multicasting and online NFV-enabled multicasting problems. We then devise the very first approximation algorithm with an approximation ratio of 2K for the NFV-enabled multicasting problem if the number of servers for implementing the network functions of each request is no more than a constant K (>= 1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an online algorithm with a competitive ratio of O(log n) when K = 1, where n is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms outperform other existing heuristics.

关键词： Servers Multicast communication approximation algorithms Heuristic algorithms Bandwidth Optical switches Middleboxes

来源：评论

学校读者我要写书评

暂无评论

Scheduling distributed clusters of parallel machines: Primal-dual and LP-based approximation algorithms 24

Scheduling distributed clusters of parallel machines: Primal...

引用

24th Annual European Symposium on algorithms, ESA 2016

作者： Murray, Riley Chao, Megan Khuller, Samir Department of Industrial Engineering and Operations Research University of California Berkeley United States Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology Cambridge United States Department of Computer Science University of Maryland College Park United States

ISBN: (纸本)9783959770156

The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem. © Riley Murray, Samir Khuller, and Megan Chao.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast approximation algorithms for the generalized survivable network design problem 27

Fast approximation algorithms for the generalized survivable...

引用

27th International Symposium on algorithms and Computation, ISAAC 2016

作者： Feldmann, Andreas Emil Könemann, Jochen Pashkovich, Kanstantsin Sanità, Laura Charles University Prague Czech Republic Dept. of Combinatorics and Optimization University of Waterloo Canada

ISBN: (纸本)9783959770262

In a standard f-connectivity network design problem, we are given an undirected graph G = (V, E), a cut-requirement function f : 2V → N, and non-negative costs c(e) for all e ∈ E. We are then asked to find a minimum-cost vector x ∈ E such that x(δ(S)) ≥ f(S) for all S ⊆ V. We focus on the class of such problems where f is a proper function. This encodes many well-studied NP-hard problems such as the generalized survivable network design problem. In this paper we present the first strongly polynomial time FPTAS for solving the LP relaxation of the standard IP formulation of the f-connectivity problem with general proper functions f. Implementing Jain's algorithm, this yields a strongly polynomial time (2 + Ε)-approximation for the generalized survivable network design problem (where we consider rounding up of rationals an arithmetic operation). © Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, and Laura Sanità.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact and approximation algorithms for weighted matroid intersection 27

Exact and approximation algorithms for weighted matroid inte...

引用

27th Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2016

作者： Huang, Chien-Chung Kakimura, Naonori Kamiyama, Naoyuki Department ot Computer Science and Engineering Chalmers University of Technology Sweden Graduate School of Arts and Sciences University of Tokyo Japan Institute of Mathematics for Industry Kyushu University Japan

ISBN: (纸本)9781510819672

In this paper, we propose new exact and approximation algorithms for the weighted matroid intersection problem. Our exact algorithm is faster than previous algorithms when the largest weight is relatively small. Our approximation algorithm delivers a (1 - ϵ)-approximate solution with a running time significantly faster than known exact algorithms. The core of our algorithms is a decomposition technique: we decompose an instance of the weighted matroid intersection problem into a set of instances of the unweighted matroid intersection problem. The computational advantage of this approach is that we can make use of fast unweighted matroid intersection algorithms as a black box for designing algorithms. Precisely speaking, we prove that we can solve the weighted matroid intersection problem via solving W instances of the unweighted matroid intersection problem, where W is the largest given weight. Furthermore, we can find a (1 - ϵ)-approximate solution via solving O(ϵ-1 log r) instances of the unweighted matroid intersection problem, where r is the smallest rank of the given two matroids. Our algorithms are simple and flexible: they can be adapted to special cases of the weighted matroid intersection problem, using specialized unweighted matroid intersection algorithms. In this paper, we will show the following results. 1. Given two general matroids, using Cunningham's algorithm, we can solve the weighted matroid intersection problem exactly in O(τWnr1.5) time and (1 - ϵ)-approximately in O(τϵ-1nr1.5 logr) time, where n is the size of the ground set and r is the time complexity of an independence oracle call. 2. Given two graphic matroids, using the algorithm of Gabow and Xu, we can solve the weighted matroid intersection problem exactly in O(W√rn log r) time and (1 - ϵ)-approximately in O(ϵ-1 √rn log2r) time. 3. Given two linear matroids (in the form of two r-by-n matrices), using the algorithm of Cheung, Kwok, and Lau, we can solve the weighted matroid intersection p

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Fragmenting a Graph Against a Stochastically-Located Threat

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 96-134页

作者： Shmoys, David B. Spencer, Gwen Cornell Univ Sch ORIE Ithaca NY 14853 USA Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Dartmouth Coll Neukom Inst Hanover NH 03755 USA

Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochastic optimization problems. We study several models in which we are given a graph with edge costs and node values, a budget, and a probabilistic distribution over ignition nodes: the goal is to find a budget-limited set of edges whose removal protects the largest expected value from being reachable from a stochastic ignition node. In particular, 2-stage stochastic models capture the tradeoffs between preventative treatment and real-time response. The resulting stochastic cut problems are interesting in their own right, and capture a number of related interdiction problems, both in the domain of computational sustainability, and beyond. In trees, even the deterministic problem is (weakly) NP hard: we give a Polynomial-time approximation scheme for the single-stage stochastic case in trees when the number of scenarios is constant. For the 2-stage stochastic model in trees we give a -approximation in trees which violates the budget by a factor of at most 2 (delta is the tree diameter), and a 0.387-approximation that is budget-balanced. For the single-stage stochastic case in trees we can save (1- (1 - 1/delta) (delta)) OPT without violating the budget. Single-stage results extend to general graphs with an additional O(log n) loss in budget-balancedness. Multistage results have a similar extension when the number of scenarios is constant. In an extension of the single-stage model where both ignition and spread are stochastic we give a -approximation in trees. Our approximation guarantees in trees also hold for multistage and probabilistic-element-failure generalizations of the Maximum Coverage with Knapsack Constraint problem (MCKP).

关键词： approximation algorithms Multistage Stochastic Optimization Graphs Containing contagion Sustainability

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Min-Max Cycle Cover Problems

引用

IEEE TRANSACTIONS ON COMPUTERS 2015年第3期64卷 600-613页

作者： Xu, Wenzheng Liang, Weifa Lin, Xiaola Sun Yat Sen Univ Sch Informat Sci & Technol Guangzhou 51006 Guangdong Peoples R China Australian Natl Univ Res Sch Comp Sci Canberra ACT 0200 Australia

As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph G and an integer k > 0, we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in G with an aim to find k rootless (or rooted) edge-disjoint cycles covering the vertices in V such that the maximum cycle weight among the k cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a (5 1/3 + epsilon)-approximation algorithm;for the uncapacitated rooted min-max cycle cover problem, we devise a (6 1/3 + epsilon)-approximation algorithm;and for the capacitated rooted min-max cycle cover problem, we propose a (7 + epsilon)-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6 + epsilon, 7 + epsilon, and 13 + epsilon, respectively, where epsilon is a constant with 0 < + < 1. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.

关键词： Wireless sensor networks data gathering mobile sinks vehicle routing problem min-max cycle cover tree decomposition approximation algorithms combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for k-submodular function maximization 27

Improved approximation algorithms for k-submodular function ...

引用

27th Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2016

作者： Iwata, Satoru Tanigawa, Shin-Ichi Yoshida, Yuichi Department of Mathematical Informatics University of Tokyo Japan Research Institute for Mathematical Sciences Kyoto University Centrum Wiskunde and Informatica Japan National Institute of Informatics and Preferred Infrastructure Inc. Japan

ISBN: (纸本)9781510819672

This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max{l/3,1/(1+ a)}-approximation by Ward and Živný [18], where a = max{l, √(k - l)/4}. We also show that for monotone k-submodular functions there is a polynomial-time k/(2k - l)-approximation algorithm while for any ϵ > 0 a ((k + l)/2k + ϵ)-approximation algorithm for maximizing monotone/e-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skewbisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Model-Based Compressive Sensing

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2015年第9期61卷 5129-5147页

作者： Hegde, Chinmay Indyk, Piotr Schmidt, Ludwig MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS (model-CS) leverages additional structure in the signal and provides new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models. However, for any given model, model-CS requires an algorithm that solves the model-projection problem: given a query signal, report the signal in the model that is closest to the query signal. Often, this optimization can be computationally very expensive. Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. As a result, the model-projection problem poses a fundamental obstacle for extending model-CS to many interesting classes of models. In this paper, we introduce a new framework that we call approximation-tolerant model-CS. This framework includes a range of algorithms for sparse recovery that require only approximate solutions for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-CS, thereby extending model-CS to a much wider class of signal models. Interestingly, all our algorithms involve both the minimization and the maximization variants of the model-projection problem. We instantiate this new framework for a new signal model that we call the constrained earth mover distance (CEMD) model. This model is particularly useful for signal ensembles, where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. We develop novel approximation algorithms for both the maximization and the minimization versions of the model-projection problem via graph optimization techniques. Leveraging these algorithms and our framework results in a nearly sample-optimal sparse recove

关键词： Compressed sensing approximation algorithms combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for maximum independent set of a unit disk graph

引用

INFORMATION PROCESSING LETTERS 2015年第3期115卷 439-446页

作者： Das, Gautam K. De, Minati Kolay, Sudeshna Nandy, Subhas C. Sur-Kolay, Susmita Indian Inst Technol Guwahati Dept Math Gauhati India Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Inst Math Sci Madras 600113 Tamil Nadu India Indian Stat Inst Kolkata India

We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(n logn) time using O(n) space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer k > 1, it produces a solution of size 1/(1+1/k)(2) vertical bar OPT vertical bar in O(k(4)n(sigma k) (logk) + nlogn) time and O(n + klogk) space, where OPT is the subset of disks in an optimal solution and ak sigma k <= 2. For a penny graph, the proposed PTAS produces a solution of size 1/(1+1/k) vertical bar OPT vertical bar in O(2(2 sigma k)nk + nlogn) time using O(2(2 sigma k)+n) space. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Maximum independent set Unit disk graph approximation algorithms PTAS Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Integrality gaps and approximation algorithms for dispersers and bipartite expanders 27

Integrality gaps and approximation algorithms for dispersers...

引用

27th Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2016

作者： Chen, Xue Department of Computer Science University of Texas at Austin United States

ISBN: (纸本)9781510819672

We study the problem of approximating the quality of a disperser. A bipartite graph G on ([N], [M]) is a (ρN, (1 -δ)M)-disperser if for any subset S ⊆ [N] of size ρN, the neighbor set Γ (S) contains at least (1-δ)M distinct vertices. Our main results are strong integrality gaps in the Lasserre hierarchy and an approximation algorithm for dispersers. 1. For any α > 0, δ > 0, and a random bipartite graph G with left degree D = O(logN), we prove that the Lasserre hierarchy cannot distinguish whether G is an (Nα, (1 - δ)M)-disperser or not an (N1-α.δM)-disperser. 2. For any ρ > 0, we prove that there exist infinitely many constants d such that the Lasserre hierarchy cannot distinguish whether a random bipartite graph G with right degree d is a (ρN, (1 - (1 - ρ)d)M)-disperser or not a (ρN,(1 - ω(1-ρ/ ρd+1-ρ))M)-disperser. We also provide an efficient algorithm to find a subset of size exact pN that has an approximation ratio matching the integrality gap within an extra loss of min{ρ/1-ρ,1-ρ/ ρ}/log d. Our method gives an integrality gap in the Lasserre hierarchy for bipartite expanders with left degree D. G on ([N],[M]) is a (ρN, α)-expander if for any subset S ⊆ [N] of size ρN, the neighbor set Γ(s) contains at least a · ρN distinct vertices. We prove that for any constant ∈ > 0, there exist constants ∈′ > ∈, ρ, and D such that the Lasserre hierarchy cannot distinguish whether a bipartite graph on ([N], [M]) with left degree D is a (ρTV, (1 - ∈′)D)-*** or not a (ρN, (1 - ∈)Z))-expander. © (2016) by SIAM: Society for Industrial and Applied Mathematics.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：