Greedy MaxCut algorithms and their information content
| Autor: | Yatao Bian, Alexey Gronskiy, Joachim M. Buhmann |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
FOS: Computer and information sciences
Vertex (graph theory) GRAPHENZERLEGUNG (GRAPHENTHEORIE) Discrete Mathematics (cs.DM) Computer Science - Information Theory Maximum coverage problem ALGORITHMIC COMPLEXITY (MATHEMATICS) Data processing computer science Robustness (computer science) GRAPH PARTITIONING (GRAPH THEORY) Computer Science - Data Structures and Algorithms Edge contraction PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS Data Structures and Algorithms (cs.DS) Greedy algorithm PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME Mathematics Information Theory (cs.IT) Graph partition Algorithm design ddc:004 ALGORITHMISCHE KOMPLEXITÄT (MATHEMATIK) Heuristics Algorithm Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Proceedings of the IEEE Information Theory Workshop (ITW 2015) |
| DOI: | 10.1109/itw.2015.7133122 |
| Popis: | MAXCUT defines a classical NP-hard problem for graph partitioning and it serves as a typical case of the symmetric non-monotone Unconstrained Submodular Maximization (USM) problem. Applications of MAXCUT are abundant in machine learning, computer vision and statistical physics. Greedy algorithms to approximately solve MAXCUT rely on greedy vertex labelling or on an edge contraction strategy. These algorithms have been studied by measuring their approximation ratios in the worst case setting but very little is known to characterize their robustness to noise contaminations of the input data in the average case. Adapting the framework of Approximation Set Coding, we present a method to exactly measure the cardinality of the algorithmic approximation sets of five greedy MAXCUT algorithms. Their information contents are explored for graph instances generated by two different noise models: the edge reversal model and Gaussian edge weights model. The results provide insights into the robustness of different greedy heuristics and techniques for MAXCUT, which can be used for algorithm design of general USM problems. This is a longer version of the paper published in 2015 IEEE Information Theory Workshop (ITW) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|