 Award ID(s):
 1637534
 Publication Date:
 NSFPAR ID:
 10109986
 Journal Name:
 2018 Proceedings of the Eighth SIAM Workshop on Combinatorial Scientific Computing
 Sponsoring Org:
 National Science Foundation
More Like this

We describe a paradigm for designing parallel algorithms via approximation, and illustrate it on the bedgecover problem. A bedgecover of minimum weight in a graph is a subset $C$ of its edges such that at least a specified number $b(v)$ of edges in $C$ is incident on each vertex $v$, and the sum of the edge weights in $C$ is minimum. The Greedy algorithm and a variant, the LSE algorithm, provide $3/2$approximation guarantees in the worstcase for this problem, but these algorithms have limited parallelism. Hence we design two new $2$approximation algorithms with greater concurrency. The MCE algorithm reduces the computation of a bedgecover to that of finding a b'matching, by exploiting the relationship between these subgraphs in an approximation context. The LSENW is derived from the LSEalgorithm using static edge weights rather than dynamically computing effective edge weights. This relaxation gives LSE a worse approximation guarantee but makes it more amenable to parallelization. We prove that both the MCE and LSENW algorithms compute the same bedgecover with at most twice the weight of the minimum weight edge cover. In practice, the $2$approximation and $3/2$approximation algorithms compute edge covers of weight within $10\%$ the optimal. We implement three of themore »

We describe a 3/2approximation algorithm, \lse, for computing a bedgecover of minimum weight in a graph with weights on the edges. The bedgecover problem is a generalization of the betterknown Edge Cover problem in graphs, where the objective is to choose a subset C of edges in the graph such that at least a specified number b(v) of edges in C are incident on each vertex v. In the weighted bedgecover problem, we minimize the sum of the weights of the edges in C. We prove that the Locally Subdominant edge (LSE) algorithm computes the same bedge cover as the one obtained by the Greedy algorithm for the problem. However, the Greedy algorithm requires edges to be sorted by their effective weights, and these weights need to be updated after each iteration. These requirements make the Greedy algorithm sequential and impractical for massive graphs. The LSE algorithm avoids the sorting step, and is amenable for parallelization. We implement the algorithm on a serial machine and compare its performance against a collection of approximation algorithms for the bedge cover problem. Our results show that the algorithm is 3 to 5 times faster than the Greedy algorithm on a serial processor. Themore »

We consider the maximum vertexweighted matching problem (MVM), in which nonnegative weights are assigned to the vertices of a graph, and the weight of a matching is the sum of the weights of the matched vertices. Although exact algorithms for MVM are faster than exact algorithms for the maximum edgeweighted matching problem, there are graphs on which these exact algorithms could take hundreds of hours. For a natural number k, we design a k/(k + 1)approximation algorithm for MVM on nonbipartite graphs that updates the matching along certain short paths in the graph: either augmenting paths of length at most 2k + 1 or weightincreasing paths of length at most 2k. The choice of k = 2 leads to a 2/3approximation algorithm that computes nearly optimal weights fast. This algorithm could be initialized with a 2/3approximate maximum cardinality matching to reduce its runtime in practice. A 1/2approximation algorithm may be obtained using k = 1, which is faster than the 2/3approximation algorithm but it computes lower weights. The 2/3approximation algorithm has time complexity O(Δ2m) while the time complexity of the 1/2approximation algorithm is O(Δm), where m is the number of edges and Δ is the maximum degree of a vertex.more »

Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground set
N , a weight function ,$$w: N \rightarrow \mathbb {R}_+$$ $w:N\to {R}_{+}$r monotone submodular functions over$$f_1,f_2,\ldots ,f_r$$ ${f}_{1},{f}_{2},\dots ,{f}_{r}$N and requirements the goal is to find a minimum weight subset$$k_1,k_2,\ldots ,k_r$$ ${k}_{1},{k}_{2},\dots ,{k}_{r}$ such that$$S \subseteq N$$ $S\subseteq N$ for$$f_i(S) \ge k_i$$ ${f}_{i}\left(S\right)\ge {k}_{i}$ . We refer to this problem as$$1 \le i \le r$$ $1\le i\le r$MultiSubmodCover and it was recently considered by HarPeled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260 HarPeled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$ $r=1$MultiSubmodCover generalizes the wellknown Submodular Set Cover problem (SubmodSC ), and it can also be easily reduced toSubmodSC . A simple greedy algorithm gives an approximation where$$O(\log (kr))$$ $O(log(kr\left)\right)$ and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm for$$k = \sum _i k_i$$ $k={\sum}_{i}{k}_{i}$MultiSubmodCover that covers each constraint to within a factor of while incurring an approximation of$$(11/e\varepsilon )$$ $(11/e\epsilon )$ in the cost. Second, we consider the special case when each$$O(\frac{1}{\epsilon }\log r)$$ $O(\frac{1}{\u03f5}logr)$ is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover ($$f_i$$ ${f}_{i}$PartialSC ), covering integer programs (CIPs ) and multiple vertex cover constraintsmore » 
We consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))time algorithm that returns a (1+epsilon)approximate estimate of the MST cost. This result immediately implies an O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any epsilon > 0. However, no o(n^2)time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problemmore »