35924921
Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts
For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 − 3/k for an odd k and 2 − (3k − 4)/(k2 − k) for an even k. The running time is O(kmn3 log(n2/m)) where n and m are the numbers of vertices and edges respectively.
18420967
A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraph
Given a hypergraph with nonnegative costs on hyperedge and a requirement function r : 2V → Z+, where V is the vertex set, we consider the problem of finding a minimum cost hyperedge set F such that for all S ⊆ V, F contains at least r(S) hyperedges incident to S. In the case that r is weakly supermodular (i.e., r(V) = 0 and r(A) + r(B) ≤ max{r(A ∩ B) + r(A ∪ B); r(A - B) + r(B - A)} for any A;B ⊆ V), and the so-called minimum violated sets can be computed in polynomial time, we present a primal-dual approximation algorithm with performance guarantee dmaxH(rmax), where dmax is the maximum degree of the hyperedges with positive cost, rmax is the maximum requirement, and H(i) = Σi=1i 1/j is the harmonic function. In particular, our algorithm can be applied to the survivable network design problem in which the requirement is that there should be at least rst hyperedge-disjoint paths between each pair of distinct vertices s and t, for which rst is prescribed.
6425229
A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem
A linear time 5/3-approximation algorithm is presented for the NP-hard problem of finding a minimum strongly-connected spanning subgraph. It is based on cycle contraction that was first introduced by Khuller, Raghavachari and Young [SIAM J. Comput. 24 (1995) 859-872]. We improve their result by contracting special cycles and utilizing a more efficient data structure.
486376
Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts
For an edge weighted undirected graph G and an integer k ≥ 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts.We show that the performance ratio of our algorithm is 2 - 3/k for an odd k and 2 - (3k - 4)/(k2 - k) for an even k. The running time is O(kmn3 log(n2/m)) where n and m are the numbers of vertices and edges respectively.
41378670
A Unified Framework for Approximating Multiway Partition Problems
We present a simple and unified framework for developing and analyzing approximation algorithms for some multiway partition problems (with or without terminals), including the k-way cut (or kcut), multiterminal cut (or multiway cut), hypergraph partition and target split.
13553903
Greedy splitting algorithms for approximating multiway partition problems
Abstract.Given a system (V,T,f,k), where V is a finite set, is a submodular function and k≥2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition ={V1,V2,...,Vk} of V that satisfiesfor all i and minimizes f(V1)+f(V2)+···+f(Vk), where is a k-partition of hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.
17699590
Adapting K-Means Algorithm for Discovering Clusters in Subspaces
Subspace clustering is a challenging task in the field of data mining. Traditional distance measures fail to differentiate the furthest point from the nearest point in very high dimensional data space. To tackle the problem, we design minimal subspace distance which measures the similarity between two points in the subspace where they are nearest to each other. It can discover subspace clusters implicitly when measuring the similarities between points. We use the new similarity measure to improve traditional k-means algorithm for discovering clusters in subspaces. By clustering with low-dimensional minimal subspace distance first, the clusters in low-dimensional subspaces are detected. Then by gradually increasing the dimension of minimal subspace distance, the clusters get refined in higher dimensional subspaces. Our experiments on both synthetic data and real data show the effectiveness of the proposed similarity measure and algorithm.
19000804
Receive Side Coalescing for Accelerating TCP/IP Processing
With rapid advancements in Ethernet technology, Ethernet speeds have increased by 10 fold, from 1 to 10Gbps, in a period of 2-3 years. This sudden increase in speeds has outpaced the rate at which processor and memory speeds have been increasing, raising concerns that TCP/IP processing will not scale to these levels. As a result, applications running on commercial servers will not be able to take advantage of the increased Ethernet bandwidth. This has led to a flurry of activity in the industry and academia focused on finding ways to scale up TCP/IP processing to 10Gbps and beyond. In this paper, we propose a novel technique called "Receive Side Coalescing" (RSC) that increases TCP/IP processing efficiencies significantly. RSC allows NICs to identify packets that belong to same TCP/IP flow and coalesce them into a single large packet. As a result, TCP/IP stack has to process fewer packets reducing per packet processing costs. NIC can do this coalescing of packets during interrupt moderation time hence packet latency is not affected. We have collected packet traces and analyzed those to find out how much coalescing is possible in different scenarios. Our analysis shows that about 50% reduction in number of packets is possible. We have prototyped RSC on Windows and Linux to understand the benefits, and the results show that 2-7% of savings in CPU utilization is possible at 1Gbps speeds. Projection models developed to estimate processing costs at 10Gbps show that RSC can save up to 20% of the CPU.
14270828
A Strict Approach to Approximating Lognormal Sum Distributions
In this paper, the least squares (LS) approximation approach is applied to solve the approximation problem of a sum of lognormal random variables (RV). The least squares curve fitting technique is first used to obtain the approximated closed-form pdf of the sum RV. The second time use of the least squares curve fitting technique brings the explicit closed-form expressions of the coefficients as a function of the number of the summands and the dB spread of the summands. Simulation results show that the proposed approximation exhibits a good match with the simulation results in the interested range of the distributions of the summands. Furthermore, errors due to a mixed use of the sum RV in the domain of the original variable and the domain of the logarithm are pointed out and the corrected results are presented
1276144
Hardware support for bulk data movement in server platforms
Bulk data movement occurs commonly in server work-loads and their performance is rather poor on today's microprocessors. We propose the use of small dedicated copy engines, and present a detailed analysis of a bulk data copy engine architecture. We describe the hardware support required to implement the copy engine and to tightly integrate it into server platforms. Our evaluation is based on an execution driven simulator that was extended with detailed models of bulk data movement engines. The simulation results show that dedicated engines are quite effective in eliminating the data movement overhead and are an attractive choice for handling bulk data in future high performance server platforms.
1964724
Optimal construction of edge-disjoint paths in random regular graphs
Given a graph G = (V, E) and a set of κ pairs of vertices in V, we are interested in finding, for each pair (ai, bi), a path connecting ai to bi such that the set of κ paths so found is edge-disjoint. (For arbitrary graphs the problem is NP-complete, although it is in P if κ is fixed.)We present a polynomial time randomized algorithm for finding edge-disjoint paths in the random regular graph Gn,r, for sufficiently large r. (The graph is chosen first, then an adversary chooses the pairs of end-points.) We show that almost every Gn,r is such that all sets of κ = Ω(n/log n) pairs of vertices can be joined. This is within a constant factor of the optimum.