Počet záznamů: 1
Tight Bounds on the Radius of Nonsingularity
- 1.
SYSNO ASEP 0459146 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Tight Bounds on the Radius of Nonsingularity Tvůrce(i) Hartman, David (UIVT-O) RID, SAI, ORCID
Hladík, M. (CZ)Zdroj.dok. Scientific Computing, Computer Arithmetic, and Validated Numerics. Revised Selected Papers. - Cham : Springer, 2016 / Nehmeier M. ; Wolff von Gudenberg J. ; Tucker W. - ISSN 0302-9743 - ISBN 978-3-319-31768-7 Rozsah stran s. 109-115 Poč.str. 7 s. Forma vydání Tištěná - P Akce SCAN 2014. International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics /16./ Datum konání 21.09.2014 - 26.09.2014 Místo konání Würzburg Země DE - Německo Typ akce WRD Jazyk dok. eng - angličtina Země vyd. CH - Švýcarsko Klíč. slova radius of nonsingularity ; bounds ; semidefinite programming Vědní obor RIV IN - Informatika CEP GA13-17187S GA ČR - Grantová agentura ČR Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000440867900009 EID SCOPUS 84963864062 DOI 10.1007/978-3-319-31769-4_9 Anotace Radius of nonsingularity of a square matrix is the minimal distance to a singular matrix in the maximum norm. Computing the radius of nonsingularity is an NP-hard problem. The known estimations are not very tight; one of the best one has the relative error 6n. We propose a randomized approximation method with a constant relative error 0.7834. It is based on a semidefinite relaxation. Semidefinite relaxation gives the best known approximation algorithm for MaxCut problem, and we utilize similar principle to derive tight bounds on the radius of nonsingularity. This gives us rigorous upper and lower bounds despite randomized character of the algorithm. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2017
Počet záznamů: 1