The k-forest problem is a common generalization of both the k-MST and the dense- @math -subgraph problems. Formally, given a metric space on @math vertices @math , with @math demand pairs @math and a target'' @math , the goal is to find a minimum cost subgraph that connects at least @math demand pairs. In this paper, we give an @math -approximation algorithm for @math -forest, improving on the previous best ratio of @math by Segev & Segev. We then apply our algorithm for k-forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an @math point metric space with @math objects each with its own source and destination, and a vehicle capable of carrying at most @math objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We prove that an @math -approximation algorithm for the @math -forest problem implies an @math -approximation algorithm for Dial-a-Ride. Using our results for @math -forest, we get an @math - approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an @math -approximation by Charikar & Raghavachari; our results give a different proof of a similar approximation guarantee--in fact, when the vehicle capacity @math is large, we give a slight improvement on their results.
Dense @math -subgraph: The problem is a generalization of the problem @cite_8 , as shown in @cite_20 . The best known approximation guarantee for the problem is @math where @math is some constant, due to @cite_8 , and obtaining an improved guarantee has been a long standing open problem. Strictly speaking, @cite_8 study a potentially harder problem: the version of , where one wants to pick @math vertices to maximize the number of edges in the induced graph. However, nothing better is known even for the version of (where one wants to pick the minimum number of vertices that induce @math edges), which is a special case of @math -forest. The @math -forest problem is also a generalization of @math -MST, for which a 2-approximation is known (Garg @cite_14 ).
@cite_14 @cite_20 @cite_8
1500932665 2266714125 2161190897 2890196309
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a "target" k ≤ m, the goal is to find a minimum cost subgraph that connects at least k demand pairs. In this paper, we give an O(min √n,√k )- approximation algorithm for k-forest, improving on the previous best ratio of O(min n2 3,√m log n) by Segev and Segev [20]. We then apply our algorithm for k-forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an n point metric space with m objects each with its own source and destination, and a vehicle capable of carrying at most k objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We prove that an a-approximation algorithm for the k-forest problem implies an O(αċlog2 n)-approximation algorithm for Dial-a-Ride. Using our results for k-forest, we get an O(min √n,√k ċlog2 n)-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an O(√k log n)-approximation by Charikar and Raghavachari [5]; our results give a different proof of a similar approximation guarantee-- in fact, when the vehicle capacity k is large, we give a slight improvement on their results. The reduction from Dial-a-Ride to the k-forest problem is fairly robust, and allows us to obtain approximation algorithms (with the same guarantee) for the following generalizations: (i) Non-uniform Dial-a-Ride, where the cost of traversing each edge is an arbitrary nondecreasing function of the number of objects in the vehicle; and (ii) Weighted Diala-Ride, where demands are allowed to have different weights. The reduction is essential, as it is unclear how to extend the techniques of Charikar and Raghavachari to these Dial-a-Ride generalizations. Numerous graph mining applications rely on detecting subgraphs which are large near-cliques. Since formulations that are geared towards finding large near-cliques are hard and frequently inapproximable due to connections with the Maximum Clique problem, the poly-time solvable densest subgraph problem which maximizes the average degree over all possible subgraphs "lies at the core of large scale data mining" [10]. However, frequently the densest subgraph problem fails in detecting large near-cliques in networks. In this work, we introduce the k-clique densest subgraph problem, k ≥ 2. This generalizes the well studied densest subgraph problem which is obtained as a special case for k=2. For k=3 we obtain a novel formulation which we refer to as the triangle densest subgraph problem: given a graph G(V,E), find a subset of vertices S* such that τ(S*)=max limitsS ⊆ V t(S) |S|, where t(S) is the number of triangles induced by the set S. On the theory side, we prove that for any k constant, there exist an exact polynomial time algorithm for the k-clique densest subgraph problem . Furthermore, we propose an efficient 1 k-approximation algorithm which generalizes the greedy peeling algorithm of Asahiro and Charikar [8,18] for k=2. Finally, we show how to implement efficiently this peeling framework on MapReduce for any k ≥ 3, generalizing the work of Bahmani, Kumar and Vassilvitskii for the case k=2 [10]. On the empirical side, our two main findings are that (i) the triangle densest subgraph is consistently closer to being a large near-clique compared to the densest subgraph and (ii) the peeling approximation algorithms for both k=2 and k=3 achieve on real-world networks approximation ratios closer to 1 rather than the pessimistic 1 k guarantee. An interesting consequence of our work is that triangle counting, a well-studied computational problem in the context of social network analysis can be used to detect large near-cliques. Finally, we evaluate our proposed method on a popular graph mining application. We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math . Several algorithms with an approximation guarantee of @math are known for the Set Cover problem, where @math is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into @math , and we are required to cover at least @math elements from each color class @math , using the minimum number of sets. We give a randomized LP-rounding algorithm that is an @math approximation for the Partition Set Cover problem. Here @math denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which @math is known to be sublogarithmic in @math . We also extend the LP rounding algorithm to obtain @math approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an @math -approximation for any of these problems.