Unbalanced Graph Partitioning

Li, Angsheng; Zhang, Peng
October 2013
Theory of Computing Systems;Oct2013, Vol. 53 Issue 3, p454
Academic Journal
We investigate the unbalanced cut problems. A cut ( A, B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called E k-size), where k is an input parameter. We consider two closely related unbalanced cut problems, in which the quality of a cut is measured with respect to the sparsity and the conductance, respectively. We show that even if the input graph is restricted to be a tree, the E k-Sparsest Cut problem (to find an E k-size cut with the minimum sparsity) is still NP-hard. We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity), which outputs a cut whose sparsity is at most O(log n) times the optimum and whose smaller side has size at most O(log n) k. As a consequence, this leads to a ( O(log n), O(log n))-bicriteria approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance).


Related Articles

  • Locating communities on graphs with variations in community sizes. Papadakis, Harris; Panagiotakis, Costas; Fragopoulou, Paraskevi // Journal of Supercomputing;Aug2013, Vol. 65 Issue 2, p543 

    A fundamental problem in networking and computing is community detection. Various applications like finding web communities, uncovering the structure of social networks, or even analyzing a graph's structure to uncover Internet attacks are just some of the applications for which community...

  • Density-based region search with arbitrary shape for object localisation. Ji Zhao; Deyu Meng; Jiayi Ma // IET Computer Vision;2015, Vol. 9 Issue 6, p943 

    Region search is widely used for object localisation in computer vision. After projecting the score of an image classifier into an image plane, region search aims to find regions that precisely localise desired objects. The recently proposed region search methods, such as efficient subwindow...

  • Community Identification Based on a New Approximate Personalized PageRank Algorithm. Min Han; Xianchao Zhang // Advances in Information Sciences & Service Sciences;Nov2012, Vol. 4 Issue 20, p649 

    In this paper, we study the problem of identifying communities given a seed set. At first, we modify the Approximate Personalized PageRank (APPR) algorithm to find a community with small conductance while examining only a small number of vertices. Secondly, we apply the modified APPR algorithm...

  • Implementation of Safety Instrumented Systems using Fuzzy Risk Graph Method. Ouzraoui, Nouara; Rabah, Bilal; Said, Rachid Nait; Bourarech, Mouloud // Proceedings of the International Conference on Industrial Engine;2014, p2323 

    Although the risk graph method, described by the IEC 61508 standard is widely used for the determination of Safety Integrity Levels for the Safety Instrumented Functions (SIF) which performed by Safety Instrumented Systems (SIS). This technique has limits regarding the linguistic interpretation...

  • Uniform capacitated facility location problem with random input data. Gimadi, E.; Kurochkin, A. // Journal of Mathematical Sciences;Jan2013, Vol. 188 Issue 4, p359 

    We consider the capacitated facility location problem with uniform capacitates and specific demand restrictions. Entries of the cost matrix ( g) are assumed to take random values according to discrete uniform distribution. We propose an approximation algorithm for solving this problem and...

  • The traveling salesman problem on cubic and subcubic graphs. Boyd, Sylvia; Sitters, René; Ster, Suzanne; Stougie, Leen // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p227 

    We study the traveling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem is of interest because of its relation to the famous 4/3-conjecture for metric TSP, which says that the integrality gap, i.e., the worst case ratio...

  • Min-Sum 2-Paths Problems. Fenner, Trevor; Lachish, Oded; Popa, Alexandru // Theory of Computing Systems;Jan2016, Vol. 58 Issue 1, p94 

    An orientation of an undirected graph G is a directed graph obtained by replacing each edge { u, v} of G by exactly one of the arcs ( u, v) or ( v, u). In the min-sum k -paths orientation problem, the input is an undirected graph G and ordered pairs ( s, t), where i∈{1,2,..., k}. The goal...

  • Constant Thresholds Can Make Target Set Selection Tractable. Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias // Theory of Computing Systems;Jul2014, Vol. 55 Issue 1, p61 

    Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time approximation as well as fixed-parameter algorithms. Given an undirected graph, the task is to select a...

  • Gossip Consensus Algorithm Based on Time-Varying Influence Factors and Weakly Connected Graph for Opinion Evolution in Social Networks. Lingyun Li; Jie Zhou; Demin Li; Jinde Cao; Xiaolu Zhang // Abstract & Applied Analysis;2013, p1 

    We provide a new gossip algorithm to investigate the problem of opinion consensus with the time-varying influence factors and weakly connected graph among multiple agents. What is more, we discuss not only the effect of the time-varying factors and the randomized topological structure but also...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics