The Maximum Planar Subgraph (MPS) problem asks for a planar subgraph with maximum edge cardinality of a given undirected graph. It is known to be MaxSNP-hard and the currently best known approximation algorithm achiev...
详细信息
ISBN:
(纸本)9783319445434;9783319445427
The Maximum Planar Subgraph (MPS) problem asks for a planar subgraph with maximum edge cardinality of a given undirected graph. It is known to be MaxSNP-hard and the currently best known approximation algorithm achieves a ratio of 4/9. We analyze the general limits of approximation algorithms for MPS, based either on planarity tests or on greedy inclusion of certain subgraphs. On the one hand, we cover upper bounds for the approximation ratios. On the other hand, we show NP-hardness for thereby arising subproblems, which hence must be approximated themselves. We also provide simpler proofs for two already known facts.
We provide a quasilinear time algorithm for the p-center problem with an additive error less than or equal to 3 times the input graph's hyperbolic constant. Specifically, for the graph G = (V, E) with n vertices, ...
详细信息
ISBN:
(数字)9783319497877
ISBN:
(纸本)9783319497877;9783319497860
We provide a quasilinear time algorithm for the p-center problem with an additive error less than or equal to 3 times the input graph's hyperbolic constant. Specifically, for the graph G = (V, E) with n vertices, m edges and hyperbolic constant d, we construct an algorithm for p-centers in time O(p( delta vertical bar 1)(n vertical bar m) log(2)(n)) with radius not exceeding r(p) + delta when p <= 2 and r(p) + 3 delta when p >= 3, where rp are the optimal radii. Prior work identified p-centers with accuracy r(p) + delta but with time complexity O((n(3) log(2) n + n(2)m) log(2)(diam( G))) which is impractical for large graphs.
We describe an algorithm that finds an is an element of-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the proble...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We describe an algorithm that finds an is an element of-approximate solution to a concave mixed-integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/is an element of, provided that the number of integer variables and the number of negative eigenvalues of the objective function are fixed. The running time of the proposed algorithm is expected unless P = NP.
Scaffolding is one of the main stages in genome assembly. During this stage, we want to merge contigs assembled from the paired-end reads into bigger chains called scaffolds. For this purpose, the following graph-theo...
详细信息
ISBN:
(数字)9783319398174
ISBN:
(纸本)9783319398174;9783319398167
Scaffolding is one of the main stages in genome assembly. During this stage, we want to merge contigs assembled from the paired-end reads into bigger chains called scaffolds. For this purpose, the following graph-theoretical problem has been proposed: Given an edge-weighted complete graph G and a perfect matching D of G, we wish to find a Hamiltonian path P in G such that all edges of D appear in P and the total weight of edges in P but not in D is maximized. This problem is NP-hard and the previously best polynomial-time approximation algorithm for it achieves a ratio of 1/2. In this paper, we design a new polynomial-time approximation algorithm achieving a ratio of 5-5 epsilon/9-8 epsilon for any constant 0 < epsilon < 1. Several generalizations of the problem have also been introduced in the literature and we present polynomial-time approximation algorithms for them that achieve better approximation ratios than the previous bests. In particular, one of the algorithms answers an open question.
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, s...
详细信息
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.
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 ne...
详细信息
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...
详细信息
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 a...
详细信息
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
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 stochasti...
详细信息
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).
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...
详细信息
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.
暂无评论