E-viri
Recenzirano
-
Manurangsi, Pasin
Information processing letters, December 2021, 2021-12-00, Letnik: 172Journal Article
•Linear discrepancy is shown to be Π2-hard.•The hardness holds even for approximation with any constant factor less than 9/8.•Together with a previous result of Li and Nikolov, Linear discrepancy is Π2-complete. In this note, we prove that the problem of computing the linear discrepancy of a given matrix is Π2-hard, even to approximate within 9/8−ϵ factor for any ϵ>0. This strengthens the NP-hardness result of Li and Nikolov 9 for the exact version of the problem, and answers a question posed by them. Furthermore, since Li and Nikolov showed that the problem is contained in Π2, our result makes linear discrepancy another natural problem that is Π2-complete (to approximate).
Avtor
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.