Heuristics for semirandom graph problems (Q1604213): Difference between revisions

@@ Property / DOI @@
-.1006/jcss.2001.1773
@@ Property / DOI: 10.1006/jcss.2001.1773 / rank @@
-Normal rank
@@ Property / author @@
-Q172552
@@ Property / author: Q172552 / rank @@
-Normal rank
@@ Property / author @@
+Uriel Feige
@@ Property / author: Uriel Feige / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+DIMACS
@@ Property / describes a project that uses: DIMACS / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1987178221
@@ Property / OpenAlex ID: W1987178221 / rank @@
+Normal rank
@@ Property / cites work @@
+Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
+Normal rank
@@ Property / cites work @@
+A Spectral Technique for Coloring Random 3-Colorable Graphs
+Normal rank
@@ Property / cites work @@
+Approximating the independence number via the \(\vartheta\)-function
+Normal rank
@@ Property / cites work @@
+Q4705344
@@ Property / cites work: Q4705344 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4004078
@@ Property / cites work: Q4004078 / rank @@
+Normal rank
@@ Property / cites work @@
+Coloring Random and Semi-Random k-Colorable Graphs
+Normal rank
@@ Property / cites work @@
+An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
+Normal rank
@@ Property / cites work @@
+Approximating maximum independent sets by excluding subgraphs
+Normal rank
@@ Property / cites work @@
+Q4714131
@@ Property / cites work: Q4714131 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds for the Partitioning of Graphs
@@ Property / cites work: Lower Bounds for the Partitioning of Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
+Normal rank
@@ Property / cites work @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+Finding and certifying a large hidden clique in a semirandom graph
+Normal rank
@@ Property / cites work @@
+Approximating the minimum bisection size (extended abstract)
+Normal rank
@@ Property / cites work @@
+Q3122905
@@ Property / cites work: Q3122905 / rank @@
+Normal rank
@@ Property / cites work @@
+The eigenvalues of random symmetric matrices
@@ Property / cites work: The eigenvalues of random symmetric matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+A still better performance guarantee for approximate graph coloring
+Normal rank
@@ Property / cites work @@
+Approximate graph coloring by semidefinite programming
+Normal rank
@@ Property / cites work @@
+On the Shannon capacity of a graph
@@ Property / cites work: On the Shannon capacity of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Nonpolyhedral Relaxations of Graph-Bisection Problems
+Normal rank
@@ Property / cites work @@
+Q4252731
@@ Property / cites work: Q4252731 / rank @@
+Normal rank
@@ Property / DOI @@
+.1006/JCSS.2001.1773
@@ Property / DOI: 10.1006/JCSS.2001.1773 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1604213