Approximation algorithms for semi-random partitioning problems

DOI10.1145/2213977.2214013zbMath1286.68504arXivcs/0510029OpenAlexW2039759060MaRDI QIDQ5415488

Yury Makarychev, Konstantin Makarychev, Aravindan Vijayaraghavan

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0510029

zbMATH Keywords

approximation algorithmgraph partitioningaverage-case analysisrandom planted modelsemi-random model

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (6)

Independent sets in semi-random hypergraphs ⋮ The simultaneous semi-random model for TSP ⋮ Unnamed Item ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ Unnamed Item ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

This page was built for publication: Approximation algorithms for semi-random partitioning problems