Name
Abstract | ||
|---|---|---|
Semirandom models generate problem instances by blending random and adversarial decisions, thus intermediating between the worst-case assumptions that may be overly pessimistic hi many situations, and the easy pure random case. In the G(n,p,k) random graph model, the n vertices are partitioned into k color classes each of size n/k. Then, every edge connecting two different color classes is included with probability p = p(n). In the semirandom variant, G*(n,p,k) an adversary may add edges as long as the planted coloring S respected. Feige and Killian prove that unless NP subset of BPP, no polynomial time algorithm works whp when np < (1 - epsilon) ln n, in particular when up is constant. Therefore, it seems like G*(n,p,k) is not an interesting benchmark for polynomial time algorithms designed to work whp on sparse instances (up a constant). We suggest two new criteria, using semirandom models, to serve as benchmarks for such algorithms. We also suggest two new coloring heuristics and compare them with the coloring heuristics suggested by Alon and Kahale 1997 and by Bottcher 2005. We prove that in some explicit sense both our heuristics are preferable to the latter. |
Year | Venue | Field |
|---|---|---|
2006 | SIAM Proceedings Series | Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Algorithm,Heuristics,Time complexity,Mathematics |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| michael krivelevich | 1 | 1688 | 179.90 |
| Dan Vilenchik | 2 | 143 | 13.36 |