Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Jesper Nederlof

doi:10.1007/978-3-030-42071-0_11

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Jesper Nederlof

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Hoofdstuk › Academic › peer review

6 Citaten (Scopus)

Samenvatting

We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.

Originele taal-2	Engels
Titel	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Uitgeverij	Springer
Pagina's	145-164
Aantal pagina's	20
DOI's	https://doi.org/10.1007/978-3-030-42071-0_11
Status	Gepubliceerd - 2020

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12160 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Bibliografische nota

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.

Financiering

Supported by the Netherlands Organization for Scientific Research under project no. 024.002.003 and the European Research Council under project no. 617951.

Financiers	Financiernummer
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003
European Union’s Horizon Europe research and innovation programme	853234
European Research Council	617951

Toegang tot document

10.1007/978-3-030-42071-0_11

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

Nederlof, J. (2020). Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (blz. 145-164). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12160 LNCS). Springer. https://doi.org/10.1007/978-3-030-42071-0_11

Nederlof, Jesper. / Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, 2020. blz. 145-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{9fb531599c2f4c67b721bf53ae22ceca,

title = "Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices",

abstract = "We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.",

author = "Jesper Nederlof",

note = "Funding Information: Supported by the Netherlands Organization for Scientific Research under project no. 024.002.003 and the European Research Council under project no. 617951. Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.",

year = "2020",

doi = "10.1007/978-3-030-42071-0_11",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "145--164",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Nederlof, J 2020, Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12160 LNCS, Springer, blz. 145-164. https://doi.org/10.1007/978-3-030-42071-0_11

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. / Nederlof, Jesper.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, 2020. blz. 145-164 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12160 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Hoofdstuk › Academic › peer review

TY - CHAP

T1 - Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

AU - Nederlof, Jesper

N1 - Funding Information: Supported by the Netherlands Organization for Scientific Research under project no. 024.002.003 and the European Research Council under project no. 617951. Publisher Copyright: © 2020, Springer Nature Switzerland AG.

PY - 2020

Y1 - 2020

N2 - We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.

AB - We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on associated partial solutions matrices may directly lead to speedups.

UR - http://www.scopus.com/inward/record.url?scp=85090012641&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-42071-0_11

DO - 10.1007/978-3-030-42071-0_11

M3 - Chapter

AN - SCOPUS:85090012641

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 145

EP - 164

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer

ER -

Nederlof J. Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer. 2020. blz. 145-164. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-42071-0_11

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Samenvatting

Publicatie series

Bibliografische nota

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit