E-viri
Recenzirano
Odprti dostop
-
Coja-Oghlan, Amin; Efthymiou, Charilaos
Random structures & algorithms, October 2015, Letnik: 47, Številka: 3Journal Article
The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be (2−εd)nln(d)/d≤α(G(n,m))≤(2+εd)nln(d)/d with high probability, with εd→0 in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size nln(d)/d, i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size (1+ε)nln(d)/d for any fixed ε>0 (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point k∼nln(d)/d. Roughly speaking, we prove that independent sets of size k>(1+ε)nln(d)/d form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.