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

Dense steiner problems: approximation algorithms and inapproximability

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Karpinski, Marek Lewandowski, Mateusz Meesum, Syed Mohammad Mnich, Matthias Universität Bonn Institut für Informatik Bonn Germany University of Wrocaw Institute of Computer Science Wrocaw Poland Tu Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Steiner Tree problem is a classical problem in com-binatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ|V(G) \ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T1,... ,Tkare connected, and every terminal in Tihas at least δ|Tj| neighbours in Tj, and at least δ|S| nodes in S = V(G) \ (T1∪ · · · ∪ Tk), for each i,j in {1,... , k} with i ≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a (13/12 + ϵ)-approximation algorithm for δ = 1/2 and any ϵ > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for coordinating ad campaigns on social networks

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Lakhotia, Kartik Kempe, David University of Southern California

We study a natural model of coordinated social ad campaigns over a social network, based on models of Datta et al. and Aslay et al. Multiple advertisers are willing to pay the host — up to a known budget — per user exposure, whether that exposure is sponsored or organic (i.e., shared by a friend). Campaigns are seeded with sponsored ads to some users, but no network user must be exposed to too many sponsored ads. As a result, while ad campaigns proceed independently over the network, they need to be carefully coordinated with respect to their seed sets. We study the objective of maximizing the network’s total ad revenue. Our main result is to show that under a broad class of social influence models, the problem can be reduced to maximizing a submodular function subject to two matroid constraints;it can therefore be approximated within a factor essentially 12 in polynomial time. When there is no bound on the individual seed set sizes of advertisers, the constraints correspond only to a single matroid, and the guarantee can be improved to 1 − 1/e;in that case, a factor 21 is achieved by a practical greedy algorithm. The 1 − 1/e approximation algorithm for the matroid-constrained problem is far from practical;however, we show that specifically under the Independent Cascade model, LP rounding and Reverse Reachability techniques can be combined to obtain a 1−1/e approximation algorithm which scales to several tens of thousands of nodes. Our theoretical results are complemented by experiments evaluating the extent to which the coordination of multiple ad campaigns inhibits the revenue obtained from each individual campaign, as a function of the similarity of the influence networks and the strength of ties in the network. Our experiments suggest that as networks for different advertisers become less similar, the harmful effect of competition decreases. With respect to tie strengths, we show that the most harm is done in an intermediate range. Copyright © 2019, The Authors.

关键词： approximation algorithms

approximation algorithms for maximally balanced connected graph partition

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Chen, Yong Chen, Zhi-Zhong Lin, Guohui Xu, Yao Zhang, An Department of Mathematics Hangzhou Dianzi University Hangzhou China Division of Information System Design Tokyo Denki University Saitama Japan Department of Computing Science University of Alberta EdmontonABT6G 2E8 Canada Department of Computer Science Kettering University FlintMI United States

Given a simple connected graph G = (V, E), we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The general vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm;the vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively;but no approximability result exists for k-BGP when k ≥ 4, except a trivial k-approximation. In this paper, we present another 3/2-approximation for our cardinality 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any constant k ≥ 3. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could be useful for related graph partition problems. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for Tours of Orientation-varying View Cones

学校读者我要写书评

暂无评论

Approximation Algorithms for Tours of Orientation-varying Vi...

IEEE International Conference on Robotics and Automation (ICRA)

作者： Stefas, Nikolaos Plonski, Patrick A. Isler, Volkan Univ Minnesota Minneapolis MN 55455 USA

ISBN: (纸本)9781538630815

This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle a and height H when their apex points lie on a planar surface. This is a novel variant of the 3D Traveling Salesman Problem with intersecting Neighborhoods (TSPN) called Cone-TSPN. When the cones are allowed to tilt by an angle epsilon we have the tilted Cone-TSPN problem, to which we present an algorithm that returns a solution with an approximation ratio of O (1+tan alpha / 1-tan epsilon tan alpha (1 + log max(H)/min(H)). We demonstrate through simulations that our algorithm can be implemented in a practical way and by exploiting the structure of the cones we can achieve shorter tours. Finally, we present results from covering a reflective surface (lake area) that shows the importance of selecting different view angles under strong sunlight specularities.

关键词： approximation algorithms Three-dimensional displays Task analysis Traveling salesman problems Lakes Animals Cameras"

approximation algorithms for BalancedCC Multiwinner Rules 19

学校读者我要写书评

暂无评论

Approximation Algorithms for BalancedCC Multiwinner Rules

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

作者： Markus Brill Piotr Faliszewski Frank Sommer Nimrod Talmon TU Berlin Berlin Germany AGH University Krakow Poland Philipps-Universität Marburg Marburg Germany Ben-Gurion University Be'er Sheva Israel

ISBN: (纸本)9781450363099

X-BalancedCC multiwinner voting rules constitute an attractive but computationally intractable compromise between the proportionality provided by the Monroe rule and the diversity provided by the Chamberlin--Courant rule. We show how to use the GreedyMonroe algorithm to get improved approximation results for the X-BalancedCC rules and for the Chamberlin--Courant rule, by appropriately setting a "schedule" for the sizes of virtual districts. We describe a polynomial-time algorithm for computing a schedule that guarantees high approximation ratio, but show that finding the best possible schedule for a given election is NP-hard. We further evaluate our algorithms experimentally and show that they perform very well in practice.

关键词： multiwinner elections chamberlin--courant rule greedy algorithms monroe rule approximation algorithms

approximation algorithms for the a priori traveling repairman

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Gørtz, Inge Li Nagarajany, Viswanath Navidiz, Fatemeh Technical University of Denmark DTU Compute Denmark University of Michigan Ann ArborMI United States

We consider the a priori traveling repairman problem, which is a stochastic version of the classic traveling repairman problem (also called the traveling deliveryman or minimum latency problem). Given a metric (V;d) with a root r ϵ V , the traveling repairman problem (TRP) involves finding a tour originating from r that minimizes the sum of arrival-times at all vertices. In its a priori version, we are also given independent probabilities of each vertex being active. We want to find a master tour τ originating from r and visiting all vertices. The objective is to minimize the expected sum of arrival-times at all active vertices, when τ is shortcut over the inactive vertices. We obtain the first constant-factor approximation algorithm for a priori TRP under non-uniform probabilities. Previously, such a result was only known for uniform probabilities. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for process systems engineering

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Letsios, Dimitrios Baltean-Lugojan, Radu Ceccon, Francesco Mistry, Miten Wiebe, Johannes Misener, Ruth Department of Computing Imperial College London SW7 2AZ United Kingdom

Designing and analyzing algorithms with provable performance guarantees enables efficient optimization problem solving in different application domains, e.g. communication networks, transportation, economics, and manufacturing. Despite the significant contributions of approximation algorithms in engineering, only limited and isolated works contribute from this perspective in process systems engineering. The current paper discusses three representative, NP-hard problems in process systems engineering: (i) pooling, (ii) process scheduling, and (iii) heat exchanger network synthesis. We survey relevant results and raise major open questions. Further, we present approximation algorithms applications which are relevant to process systems engineering: (i) better mathematical modeling, (ii) problem classification, (iii) designing solution methods, and (iv) dealing with uncertainty. This paper aims to motivate further research at the intersection of approximation algorithms and process systems engineering. Copyright © 2019, The Authors. All rights reserved.

关键词： approximation algorithms

approximation algorithms for facial cycles in planar embeddings 29

学校读者我要写书评

暂无评论

Approximation algorithms for facial cycles in planar embeddi...

29th International Symposium on algorithms and Computation, ISAAC 2018

作者： Da Lozzo, Giordano Rutter, Ignaz Computer Science Department Roma Tre University Italy Department of Computer Science and Mathematics University of Passau Germany

ISBN: (纸本)9783959770941

Consider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This problem, called Max Facial C-Cycles, was first studied by Mutzel and Weiskircher [IPCO'99] and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002]. We establish a tight border of tractability for Max Facial C-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial C-Cycles. Namely, we give a 2-approximation for series-parallel graphs and a (4 + Ε)-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems. © Giordano Da Lozzo and Ignaz Rutter;licensed under Creative Commons License CC-BY

关键词： approximation algorithms

approximation algorithms for the p-Hub Center Routing Problem in Parameterized Metric Graphs 1

学校读者我要写书评

暂无评论

29th International Workshop on Combinatorial algorithms (IWOCA)

作者： Chen, Li-Hsuan Hsieh, Sun-Yuan Hung, Ling-Ju Klasing, Ralf AROBOT Innovat CO LTD New Taipei 235 Taiwan Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan Univ Bordeaux CNRS LaBRI 351 Cours Liberat F-33405 Talence France

A complete weighted graph G = (V, E, w) is called Delta beta-metric, for some beta >= 1/2, if G satisfies the beta-triangle inequality, i.e., w(u, v) 1/2. Moreover, we give 2 beta-approximation algorithms running ... 详细信息

ISBN: (数字)9783319946672

ISBN: (纸本)9783319946672;9783319946665

A complete weighted graph G = (V, E, w) is called Delta beta-metric, for some beta >= 1/2, if G satisfies the beta-triangle inequality, i.e., w(u, v) <= beta . (w(u, x) + w(x, v)) for all vertices u, v, x is an element of V. Given a Delta(beta)-metric graph G = (V, E, w), the Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H* of G such that (i) any pair of vertices in C* is adjacent in H* where C*. V and vertical bar C*vertical bar = p;(ii) any pair of vertices in V \ C* is not adjacent in H*;(iii) each v is an element of V \ C* is adjacent to exactly one vertex in C*;and (iv) the routing cost r(H*) = Sigma(u,v is an element of V) d(H)* (u, v) is minimized where d(H)* (u, v) = w(u, f* (u))+ w(f* (u), f* (v))+ w(v, f* (v)) and f* (u), f* (v) are the vertices in C* adjacent to u and v in H*, respectively. Note that w(v, f* (v)) = 0 if v is an element of C*. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. In this paper, we show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in Delta(beta)-metric graphs for any beta > 1/2. Moreover, we give 2 beta-approximation algorithms running in time O(n(2)) for any beta > 1/2 where n is the number of vertices in the input graph.

关键词： approximation algorithms