Heuristics for semirandom graph problems
From MaRDI portal
Publication:1604213
DOI10.1006/jcss.2001.1773zbMath1006.68103OpenAlexW1987178221MaRDI QIDQ1604213
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
Related Items
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
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
