Approximation algorithms for semi-random partitioning problems

DOI10.1145/2213977.2214013MaRDI QIDQ5415488zbMATH OpenOpenAlexFDO

Authors Konstantin Makarychev, Yury 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 algorithmaverage-case analysisgraph partitioningrandom planted modelsemi-random model

Mathematics Subject Classification ID

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

Abstract: In this paper we investigate the notion of conditional independence and prove several information inequalities for conditionally independent random variables.

Recommendations

• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Constant factor approximation for balanced cut in the PIE model
• Heuristics for semirandom graph problems
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 1418276

Cited in

(14)

• The simultaneous semi-random model for TSP
• Approximation algorithms for the partial assignment problem
• Randomized methods for the number partitioning problem
• Sorting noisy data with partial information
• Stochastic analysis of partitioning algorithms for matching problems
• Approximation algorithms for array partitioning problems
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Introduction to Semirandom Models
• New abilities and limitations of spectral graph bisection
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• scientific article; zbMATH DE number 7650095 (Why is no real title available?)
• The simultaneous semi-random model for TSP
• Planted models for the densest k-subgraph problem
• Independent sets in semi-random hypergraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415488)