The Minimum Bisection in the Planted Bisection Model

In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) c * sqrt((d_+)ln(d_+)) for a certain constant c>0.

• Publication year

  2015

• Venue

  Theory of Computing

• Publication date

  2015-05-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.APPROX-RANDOM.2015.710arXiv 1505.02985
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Extremal Cuts of Sparse Random Graphs

  2015cited by this paper
• How does the core sit inside the mantle?

  2015cited by this paper
• Consistency Thresholds for the Planted Bisection Model

  2014cited by this paper
• The Condensation Phase Transition in Random Graph Coloring

  2014cited by this paper
• Exact Recovery in the Stochastic Block Model

  2014cited by this paper
• Community detection thresholds and the weak Ramanujan property

  2013cited by this paper
• Belief propagation, robust reconstruction and optimal recovery of block models

  2013cited by this paper
• A Proof of the Block Model Threshold Conjecture

  2013cited by this paper
• Approximation algorithms for semi-random partitioning problems

  2012cited by this paper
• Stochastic Block Models and Reconstruction

  2012cited by this paper
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

  2011cited by this paper
• The set of solutions of random XORSAT formulae

  2011cited by this paper
• Information, Physics, and Computation

  2009influential reference
• Optimal hierarchical decompositions for congestion minimization in networks

  2008cited by this paper
• The parisi formula

  2006cited by this paper
• Spectral techniques applied to sparse random graphs

  2005cited by this paper
• A spectral heuristic for bisecting random graphs

  2005cited by this paper
• A general limit theorem for recursive algorithms and combinatorial structures

  2004cited by this paper
• The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence

  2004cited by this paper
• Expander flows, geometric embeddings and graph partitioning

  2004cited by this paper
• Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique

  2004influential reference
• Max Cut for Random Graphs with a Planted Partition

  2004cited by this paper
• Approximability of the Minimum Bisection Problem: An Algorithmic Challenge

  2002cited by this paper
• Spectral partitioning of random graphs

  2001cited by this paper
• Hill-climbing finds random planted bisections

  2001cited by this paper
• Bisecting sparse random graphs

  2001cited by this paper
• Heuristics for Semirandom Graph Problems

  2001cited by this paper
• A polylogarithmic approximation of the minimum bisection

  2000cited by this paper
• Algorithms for graph partitioning on the planted partition model

  1999cited by this paper
• Go with the winners for graph bisection

  1998cited by this paper
• The Metropolis Algorithm for Graph Bisection

  1998cited by this paper
• Information, physics, and computation

  1996cited by this paper
• Expected Complexity of Graph Partitioning Problems

  1995cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• The Solution of Some Random NP-Hard Problems in Polynomial Expected Time

  1989cited by this paper
• On the second eigenvalue of random regular graphs

  1989cited by this paper
• Eigenvalues and graph bisection: An average-case analysis

  1987cited by this paper
• Graph bisection algorithms with good average case behavior

  1984cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• Some Simplified NP-Complete Graph Problems

  1976cited by this paper
• Stockmeyer: some simplified np-complete graph problems

  1976cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper

• Bad Local Minima Exist in the Stochastic Block Model

  2024cites this paper
• On the Minimum Bisection of Random 3-Regular Graphs

  2020cites this paper
• Optimization on sparse random hypergraphs and spin glasses

  2016cites this paper