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

Fast approximation algorithms for bounded degree and crossing spanning tree problems

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Chekuri, Chandra Quanrud, Kent Torres, Manuel R. Dept. of Computer Science Univ. of Illinois Urbana-Champaign UrbanaIL61801 United States Dept. of Computer Science Purdue University West LafayetteIN47909 United States

We develop fast approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem (BD-MST) and its generalization the Crossing Spanning Tree problem (Crossing-ST). We solve the underlying LP to within a (1 + ǫ) approximation factor in near-linear time via the multiplicative weight update (MWU) technique. This yields, in particular, a near-linear time algorithm that outputs an estimate B such that B ≤ B∗ ≤ ⌈(1 + ǫ)B⌉+1 where B∗ is the minimum-degree of a spanning tree of a given graph. To round the fractional solution, in our main technical contribution, we describe a fast near-linear time implementation of swap-rounding in the spanning tree polytope of a graph. The fractional solution can also be used to sparsify the input graph that can in turn be used to speed up existing combinatorial algorithms. Together, these ideas lead to significantly faster approximation algorithms than known before for the two problems of interest. In addition, a fast algorithm for swap rounding in the graphic matroid is a generic tool that has other applications, including to TSP and submodular function maximization. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

Exact and approximation algorithms for sensor placement against DDoS attacks

学校读者我要写书评

暂无评论

Exact and approximation algorithms for sensor placement agai...

Federated Conference on Computer Science and Information Systems (FedCSIS)

作者： Konstanty Junosza-Szaniawski Dariusz Nogalski Agnieszka Wójcik Faculty of Mathematics and Information Science u1. Koszykowa 75 Warsaw University of Technology Warszawa Poland C4I Systems Department u1. Warszawska 22A Military Communication Institute Zegrze Poland

ISBN: (数字)9788395541674

ISBN: (纸本)9781728141473

In DDoS attack (Distributed Denial of Service), an attacker gains control of many network users by a virus. Then the controlled users send many requests to a victim, leading to lack of its resources. DDoS attacks are hard to defend because of distributed nature, large scale and various attack techniques. One of possible ways of defense is to place sensors in the network that can detect and stop an unwanted request. However, such sensors are expensive so there is a natural question about a minimum number of sensors and their optimal placement to get the required level of safety. We present two mixed integer models for optimal sensor placement against DDoS attacks. Both models lead to a trade-off between the number of deployed sensors and the volume of uncontrolled flow. Since above placement problems are NP-hard, two efficient heuristics are designed, implemented and compared experimentally with exact linear programming solvers.

关键词： DDoS sensor placement network safety optimization minimum multicut heuristics Distributed Denial of Service sensor placement Heuristics approximation algorithms Exact Sensors

Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Biniaz, Ahmad School of Computer Science University of Windsor Canada

Given a connected vertex-weighted graph G, the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of G that maximizes the total weight of internal nodes. This problem is NP-hard and APX-hard, with the currently best known approximation factor 1/2 (Chen et al., Algorithmica 2019). For the case of claw-free graphs, Chen et al. present an involved approximation algorithm with approximation factor 7/12. They asked whether it is possible to improve these ratios, in particular for claw-free graphs and cubic graphs. We improve the approximation factors for the MaxwIST problem in cubic graphs and claw-free graphs. For cubic graphs we present an algorithm that computes a spanning tree whose total weight of internal vertices is at least (formula presented) times the total weight of all vertices, where n is the number of vertices of G. This ratio is almost tight for large values of n. For claw-free graphs of degree at least three, we present an algorithm that computes a spanning tree whose total internal weight is at least (formula presented) times the total vertex weight. The degree constraint is necessary as this ratio may not be achievable if we allow vertices of degree less than three. With the above ratios, we immediately obtain better approximation algorithms with factors (formula presented) and (formula presented) for the MaxwIST problem in cubic graphs and claw-free graphs of degree at least three, for any ∊ > 0. In addition to improving the approximation factors, the new algorithms are relatively short compared to that of Chen et al.. The new algorithms are fairly simple, and employ a variant of the depth-first search algorithm that selects a relatively-large-weight vertex in every branching step. Moreover, the new algorithms take linear time while previous algorithms for similar problem instances are super-linear. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

Improved approximation algorithms for weighted edge coloring of graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Sannyasi, Debarsho Indian Institute of Technology Kanpur India

We study weighted edge coloring of graphs, where we are given an undirected edge-weighted general multi-graph G := (V, E) with weights w : E → [0, 1]. The goal is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. In the online setting, the edges are revealed one by one and have to be colored irrevocably as soon as they are revealed. We show that 3.39m + o(m) colors are enough when the maximum number of neighbors of a vertex over all the vertices is o(m) and where m is the maximum over all vertices of the minimum number of unit-sized bins needed to pack the weights of the incident edges to that vertex. We also prove the tightness of our analysis. This improves upon the previous best upper bound of 5m by Correa and Goemans [STOC 2004]. For the offline case, we show that for a simple graph with edge disjoint cycles, m + 1 colors are sufficient and for a multi-graph tree, we show that 1.693m + 12 colors are sufficient. © 2020, CC BY.

关键词： approximation algorithms

Solving high-order portfolios via successive convex approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Zhou, Rui Palomar, Daniel P. Clear Water Bay Kowloon Hong Kong

The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

Several approximation algorithms for Sparse Best Rank-1 approximation to Higher-Order Tensors

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Mao, Xianpeng Yang, Yuning College of Mathematics and Information Science Guangxi University Nanning530004 China

Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms;in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

Tight approximation algorithms for bichromatic graph diameter and related problems 46

学校读者我要写书评

暂无评论

Tight approximation algorithms for bichromatic graph diamete...

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

作者： Dalirrooyfard, Mina Williams, Virginia Vassilevska Vyas, Nikhil Wein, Nicole MIT CambridgeMA United States

ISBN: (纸本)9783959771092

Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node can reach all other nodes). The natural and important ST-variant considers two subsets S and T of the vertex set and lets the ST-diameter be the maximum distance between a node in S and a node in T, and the ST-radius be the minimum distance for a node of S to reach all nodes of T. The bichromatic variant is the special case in which S and T partition the vertex set. In this paper we present a comprehensive study of the approximability of ST and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including time/accuracy trade-off upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis. For instance, for Bichromatic Diameter in undirected weighted graphs with m edges, we present an Õ(m3/2) time 1 5/3-approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged. © Graham Cormode, Jacques Dark, and Christian Konrad;licensed under Creative Commons License CC-BY

关键词： approximation algorithms

Faster approximation algorithms for computing shortest cycles on weighted graphs 46

学校读者我要写书评

暂无评论

Faster approximation algorithms for computing shortest cycle...

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

作者： Ducoffe, Guillaume National Institute for Research and Development in Informatics Romania Research Institute University of Bucharest ICUB Romania University of Bucharest Romania

ISBN: (纸本)9783959771092

Given an n-vertex m-edge graph G with non-negative edge-weights, a shortest cycle of G is one minimizing the sum of the weights on its edges. The girth of G is the weight of such a shortest cycle. We obtain several new approximation algorithms for computing the girth of weighted graphs: For any graph G with polynomially bounded integer weights, we present a deterministic algorithm that computes, in Õ(n5/3 + m)-time1, a cycle of weight at most twice the girth of G. This matches both the approximation factor and - almost - the running time of the best known subquadratic-time approximation algorithm for the girth of unweighted graphs. Then, we turn our algorithm into a deterministic (2 + Ε)-approximation for graphs with arbitrary non-negative edge-weights, at the price of a slightly worse running-time in Õ(n5/3polylog(1/Ε) + m). For that, we introduce a generic method in order to obtain a polynomial-factor approximation of the girth in subquadratic time, that may be of independent interest. Finally, if we assume that the adjacency lists are sorted then we can get rid off the dependency in the number m of edges. Namely, we can transform our algorithms into an Õ(n5/3)-time randomized 4-approximation for graphs with non-negative edge-weights. This can be derandomized, thereby leading to an Õ(n5/3)-time deterministic 4-approximation for graphs with polynomially bounded integer weights, and an Õ(n5/3polylog(1/Ε))-time deterministic (4 + Ε)-approximation for graphs with non-negative edge-weights. To the best of our knowledge, these are the first known subquadratic-time approximation algorithms for computing the girth of weighted graphs. © Graham Cormode, Jacques Dark, and Christian Konrad;licensed under Creative Commons License CC-BY

关键词： approximation algorithms

A performance study of some approximation algorithms for minimum dominating set in a graph

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Li, Jonathan S. Potru, Rohan Shahrokhi, Farhad University of Texas at Austin United States University of North Texas United States

We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent LP rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. All algorithms perform better than anticipated in their theoretical analysis, and have small performance ratios, measured as the size of output divided by the LP objective lower-bound. However, each may have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 seconds of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems where LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms