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

arXiv 2019年

作者： Saikia, Parikshit Karmakar, Sushanta Department of Computer Science and Engineering Indian Institute of Technology Guwahati781039 India

The Steiner tree problem is one of the fundamental and classical problems in combinatorial optimization. In this paper we study this problem in the CONGEST ED CLIQUE model of distributed computing and present two deterministic distributed approximation algorithms for the same. The first algorithm computes a Steiner tree in Õ(n1/3) rounds and Õ(n7/3) messages for a given connected undirected weighted graph of n nodes. Note here that Õ(·) notation hides polylogarithmic factors in n. The second one computes a Steiner tree in O(S + log log n) rounds and O(S(n − t)2 + n2) messages, where S and t are the shortest path diameter and the number of terminal nodes respectively in the given input graph. Both the algorithms admit an approximation factor of 2(1 − 1/), where is the number of terminal leaf nodes in the optimal Steiner tree. For graphs with S = ω(n1/3 log n), the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with S = õ(n1/3), the second algorithm outperforms the first one in terms of the round complexity. In fact when S = O(log log n) then the second algorithm admits a round complexity of O(log log n) and message complexity of Õ(n2). To the best of our knowledge, this is the first work to study the Steiner tree problem in the CONGEST ED CLIQUE model. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Local approximation algorithms for Maximum Matching in Graphs and Hypergraphs

Distributed Local Approximation Algorithms for Maximum Match...

引用

Annual IEEE Symposium on Foundations of Computer Science

作者： David G. Harris Department of Computer Science University of Maryland College Park USA

We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank r. Our main result is a deterministic algorithm to generate a matching which is an O(r)-approximation to the maximum weight matching, running in Õ(r log Δ + log 2 Δ + log* n) rounds. (Here, the Õ() notations hides polyloglog Δ and polylog r factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). The first main application is to nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a (1+ε) approximation algorithm using Õ(log Δ/ε 3 + polylog(1/ε, log log n)) randomized time and Õ(log 2 Δ/ε 4 + log*n/ε) deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for (2Δ - 1) -edge-list coloring in Õ(log 2 Δ log n) rounds deterministically or Õ((log log n) 3 ) rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most ⌈(1+ε)λ⌉ for a graph of arboricity λ; for fixed ε this runs in Õ(log 6 n) rounds deterministically or Õ(log 3 n ) rounds randomly.

关键词： approximation algorithms Computational modeling Heuristic algorithms Computer science Graph theory Distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Adaptive Seed Minimization

arXiv

引用

arXiv 2019年

作者： Tang, Jing Huang, Keke Xiao, Xiaokui Lakshmanan, Laks V.S. Tang, Xueyan Sun, Aixin Lim, Andrew Dept. of Ind. Syst. Engg. and Mgmt. National University of Singapore School of Comp. Sci. and Engg Nanyang Technological University School of Computing National University of Singapore Department of Computer Science University of British Columbia School of Computer Science and Engineering Nanyang Technological University

As a dual problem of influence maximization, the seed minimization problem asks for the minimum number of seed nodes to influence a required number η of users in a given social network G. Existing algorithms for seed minimization mostly consider the non-adaptive setting, where all seed nodes are selected in one batch without observing how they may influence other users. In this paper, we study seed minimization in the adaptive setting, where the seed nodes are selected in several batches, such that the choice of a batch may exploit information about the actual influence of the previous batches. We propose a novel algorithm, ASTI, which addresses the adaptive seed minimization problem in O (Formula presented) expected time and offers an approximation guarantee of (1−(1−1/b)b )(1−1/e)(1−Ε ) (ln η+1)2 in expectation, where η is the targeted number of influenced nodes, b is size of each seed node batch, and Ε ∈ (0, 1) is a user-specified parameter. To the best of our knowledge, ASTI is the first algorithm that provides such an approximation guarantee without incurring prohibitive computation overhead. With extensive experiments on a variety of datasets, we demonstrate the effectiveness and efficiency of ASTI over competing methods. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Contiguous cake cutting: Hardness results and approximation algorithms

arXiv

引用

arXiv 2019年

作者： Goldberg, Paul W. Hollender, Alexandros Suksompong, Warut Department of Computer Science University of Oxford

We study the fair allocation of a cake, which serves as a metaphor for a divisible resource, under the requirement that each agent should receive a contiguous piece of the cake. While it is known that no finite envy-free algorithm exists in this setting, we exhibit efficient algorithms that produce allocations with low envy among the agents. We then establish NP-hardness results for various decision problems on the existence of envy-free allocations, such as when we fix the ordering of the agents or constrain the positions of certain cuts. In addition, we consider a discretized setting where indivisible items lie on a line and show a number of hardness results extending and strengthening those from prior work. Finally, we investigate connections between approximate and exact envy-freeness, as well as between continuous and discrete cake cutting. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for adaptive target profit maximization

arXiv

引用

arXiv 2019年

作者： Huang, Keke Tang, Jing Xiao, Xiaokui Sun, Aixin Lim, Andrew School of Comp. Sci. and Engg Nanyang Technological University Dept. of Ind.Syst. Engg. Mgmt. National University of Singapore School of Computing National University of Singapore

Given a social network G, the profit maximization (PM) problem asks for a set of seed nodes to maximize the profit, i.e., revenue of influence spread less the cost of seed selection. The target profit maximization (TPM) problem, which generalizes the PM problem, aims to select a subset of seed nodes from a target user set T to maximize the profit. Existing algorithms for PM mostly consider the nonadaptive setting, where all seed nodes are selected in one batch without any knowledge on how they may influence other users. In this paper, we study TPM in adaptive setting, where the seed users are selected through multiple batches, such that the selection of a batch exploits the knowledge of actual influence in the previous batches. To acquire an overall understanding, we study the adaptive TPM problem under both the oracle model and the noise model, and propose ADG and ADDATP algorithms to address them with strong theoretical guarantees, respectively. In addition, to better handle the sampling errors under the noise model, we propose the idea of hybrid error based on which we design a novel algorithm HATP that boosts the efficiency of ADDATP significantly. We conduct extensive experiments on real social networks to evaluate the performance, and the experimental results strongly confirm the superiorities and effectiveness of our solutions. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Minimum Power Covering Problems 16th

Improved Approximation Algorithms for Minimum Power Covering...

引用

16th International Workshop on approximation and Online algorithms (WAOA)

作者： Calinescu, Gruia Kortsarz, Guy Nutov, Zeev IIT Chicago IL 60616 USA Rutgers State Univ Camden NJ USA Open Univ Israel Raanana Israel

ISBN: (纸本)9783030046934;9783030046927

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider two network design problems under the power minimization criteria. In both problems we are given a graph G = (V, E) with edge costs and a set T subset of V of terminals. The goal is to find a minimum power edge subset F subset of E such that the graph H = (V, F) satisfies some prescribed requirements. In the MIN-POWER EDGECOVER problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1.41;the ratio is reduced to 73/60 < 1.217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/4. For all these NP-hard problems the previous best known ratio was 3/2. In the related MINPOWER TERMINAL BACKUP problem, H should contain a path from every t E T to some node in T \ {t}. We obtain ratio 3/2 for this NPhard problem, improving the trivial ratio of 2.

关键词： approximation algorithms Iterative randomized rounding Minimum power Edge-cover Terminal backup

来源：评论

学校读者我要写书评

暂无评论

On combinatorial approximation algorithms in geometry

On combinatorial approximation algorithms in geometry

引用

作者： Bruno Jartoux Universite Paris-Est

学位级别：博士

The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimisation. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of clas- sical combinatorial optimisation problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/? 2 ) gives a (1 +?) -approximation with running time n O(1/? 2 ). However the question of whether the exponent of n could be decreased to o(1/? 2 ) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems.

关键词： computational geometry combinatorial optimisation epsilon-nets approximation algorithms local search

来源：评论

学校读者我要写书评

暂无评论

Parameterized approximation algorithms for bidirected steiner network problems 26

Parameterized approximation algorithms for bidirected steine...

引用

26th European Symposium on algorithms, ESA 2018

作者： Chitnis, Rajesh Feldmann, Andreas Emil Manurangsi, Pasin University of Warwick United Kingdom Charles University Prague Czech Republic University of California Berkeley United States

ISBN: (纸本)9783959770811

The DIRECTED STEINER NETWORK (DSN) problem takes as input a directed edge-weighted graph G = (V, E) and a set D ⊆ V × V of k demand pairs. The aim is to compute the cheapest network N ⊆ G for which there is an s → t path for each (s,t) ∈ D. It is known that this problem is notoriously hard as there is no k1/4-o(1)-approximation algorithm under Gap-ETH, even when parameterizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k. For the BI-DSNPLANAR problem, the aim is to compute a planar optimum solution N ⊆ G in a bidirected graph G, i.e. for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of BI-DSNPLANAR, unless FPT=W[1]. Additionally we study several generalizations of BI-DSNPLANAR and obtain upper and lower bounds on obtainable runtimes parameterized by k. One important special case of DSN is the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem, for which the solution network N ⊆ G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under Gap-ETH there is no (2 - ϵ)-approximation algorithm parameterized by k (for any ϵ > 0). To the best of our knowledge, this is the first example of a W[1]-hard problem admitting a non-trivial parameterized approximation factor which is also known to be tight! Additionally we show that when restricting the input of SCSS to bidirected graphs, the proble

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed approximation algorithms for the minimum dominating set in KH-minor-free graphs 29

Distributed approximation algorithms for the minimum dominat...

引用

29th International Symposium on algorithms and Computation, ISAAC 2018

作者： Czygrinow, Andrzej Hanćkowiak, Michal Wawrzyniak, Wojciech Witkowski, Marcin School of Mathematical and Statistical Sciences Arizona State University TempeAZ85287-1804 United States Faculty of Mathematics and Computer Science Adam Mickiewicz University Poznań Poland

ISBN: (纸本)9783959770941

In this paper we will give two distributed approximation algorithms (in the Local model) for the minimum dominating set problem. First we will give a distributed algorithm which finds a dominating set D of size O(γ(G)) in a graph G which has no topological copy of Kh. The algorithm runs Lh rounds where Lh is a constant which depends on h only. This procedure can be used to obtain a distributed algorithm which given > 0 finds in a graph G with no Kh-minor a dominating set D of size at most (1 + )γ(G). The second algorithm runs in O(log∗ |V (G)|) rounds. © Andrzej Czygrinow, Michal Hanćkowiak, Wojciech Wawrzyniak, and Marcin Witkowski

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A successive multi-extremum approximation algorithms based on special functions in the environmental impacts researches on technogenic systems 18

A successive multi-extremum approximation algorithms based o...

引用

18th International Multidisciplinary Scientific Geoconference, SGEM 2018

作者： Petrunina, Elena Nikolskiy, Anatoliy Beloglazov, Aleksandr Pecherskij, Denis Moscow State Humanitarian and Economics University Russia

ISBN: (纸本)9786197408355

approximation of multi-extremum functions problems arise in a wide range of fields including deterministic and stochastic technics, multi-parameter optimization. The main focus of this thesis is to consider the different principle of approximation problem. Experimental definition of external impacts on complex technogenic systems is related to technical difficulties. This area of research arises from the fact that many problems of multi-extremum optimization are known to be computationally difficult (NP-hard). We propose a new approach to approximation based on the special (in particular, spherically symmetric infinite differentiable) functions. We design new approximation algorithms on structured and unstructured meshes which can be used as a tool for multi-extremum optimization. These algorithms are simple to implement and they are stable. The freedom choice of a basic function provides an opportunity to create the analytical expression for several practical models. The theoretical formulas of the proposed algorithm are derived, and the simulations results are presented. A problem of the environmental factors impacts on complex technogenic systems is used to demonstrate the possibilities of computational tools developed. The results computed for pilot studies are presented with the usage of various components of multi-extremum approximation. Furthermore, these algorithms are suitable for applying approximation techniques for implementation on parallel computers. © SGEM2018.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：