Heuristics for semirandom graph problems

DOI10.1006/JCSS.2001.1773zbMath1006.68103OpenAlexW1987178221MaRDI QIDQ1604213

Joe Kilian

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/f3663e648a626e5ea3caf20f03cf7bdd1f4596d9

zbMATH Keywords

independent setscoloringsbisections in graphssemirandom graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (27)

Independent sets in semi-random hypergraphs ⋮ Smoothed analysis of binary search trees ⋮ Are Stable Instances Easy? ⋮ The simultaneous semi-random model for TSP ⋮ A hard dial-a-ride problem that is easy on average ⋮ Spectral and structural properties of random interdependent networks ⋮ Smoothed Analysis on Connected Graphs ⋮ Online Predictions for Online TSP on the Line ⋮ Phase transitions in semidefinite relaxations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ PASS approximation: a framework for analyzing and designing heuristics ⋮ Finding large cliques in sparse semi-random graphs by simple randomized search heuristics ⋮ On percolation and ‐hardness ⋮ Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery ⋮ Graph Partitioning via Adaptive Spectral Techniques ⋮ Random Laplacian matrices and convex relaxations ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Why almost all \(k\)-colorable graphs are easy to color ⋮ Unnamed Item ⋮ On the tractability of coloring semirandom graphs ⋮ On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem ⋮ Unnamed Item ⋮ On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization ⋮ Nearly optimal robust secret sharing against rushing adversaries ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• The eigenvalues of random symmetric matrices
• Approximating maximum independent sets by excluding subgraphs
• A still better performance guarantee for approximate graph coloring
• Zero knowledge and the chromatic number
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Approximating the independence number via the \(\vartheta\)-function
• Approximating the minimum bisection size (extended abstract)
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Coloring Random and Semi-Random k-Colorable Graphs
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Finding and certifying a large hidden clique in a semirandom graph
• Lower Bounds for the Partitioning of Graphs

This page was built for publication: Heuristics for semirandom graph problems