New algorithms for a simple measure of network partitioning

DOI10.1007/978-3-031-20350-3_7OpenAlexW4313349116MaRDI QIDQ6111946

Xueyang Zhao, Binghao Yan, Peng Zhang

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-20350-3_7

zbMATH Keywords

combinatorial optimizationgraph algorithmapproximation algorithmnetwork partitioningmax \(k\)-uncut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Algorithmic aspects of homophyly of networks
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Approximation and hardness results for the max \(k\)-uncut problem
• Finding happiness: an analysis of the maximum happy vertices problem
• Improved approximation algorithms for the maximum happy vertices and edges problems
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• The maximum happy induced subgraph problem: bounds and algorithms
• On happy colorings, cuts, and structural parameterizations
• From the Cover: The structure of scientific collaboration networks
• Detecting high log-densities
• A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
• Structural Information and Dynamical Complexity of Networks
• An approximation algorithm for maxk-uncut with capacity constraints
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Approximation Algorithms for Graph Homomorphism Problems
• A Best Possible Heuristic for the k-Center Problem
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Heuristic and Special Case Algorithms for Dispersion Problems
• Finding k Cuts within Twice the Optimal
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A simple min-cut algorithm
• Community structure in social and biological networks
• A local search approximation algorithm for k-means clustering
• Least squares quantization in PCM
• Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
• A cost function for similarity-based hierarchical clustering
• Lower bounds for the happy coloring problems
• Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph

This page was built for publication: New algorithms for a simple measure of network partitioning