Balanced Graph Edge Partition
author: Milan Vojnovic,
Microsoft Research, Cambridge, Microsoft Research
published: Oct. 7, 2014, recorded: August 2014, views: 1845
published: Oct. 7, 2014, recorded: August 2014, views: 1845
Related content
Report a problem or upload files
If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Description
In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υ • n<over>k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2.
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !
Write your own review or comment: