Open problems around exact algorithms

G.J. Woeginger

doi:10.1016/j.dam.2007.03.023

Open problems around exact algorithms

G.J. Woeginger

Combinatorial Optimization 1

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

46 Citaten (Scopus)

Samenvatting

We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.

Originele taal-2	Engels
Pagina's (van-tot)	397-405
Tijdschrift	Discrete Applied Mathematics
Volume	156
Nummer van het tijdschrift	3
DOI's	https://doi.org/10.1016/j.dam.2007.03.023
Status	Gepubliceerd - 2008

Toegang tot document

10.1016/j.dam.2007.03.023

Citeer dit

@article{9fa19af1074d42c093e88319ab964f74,

title = "Open problems around exact algorithms",

abstract = "We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.",

author = "G.J. Woeginger",

year = "2008",

doi = "10.1016/j.dam.2007.03.023",

language = "English",

volume = "156",

pages = "397--405",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Open problems around exact algorithms

AU - Woeginger, G.J.

PY - 2008

Y1 - 2008

N2 - We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.

AB - We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.

U2 - 10.1016/j.dam.2007.03.023

DO - 10.1016/j.dam.2007.03.023

M3 - Article

VL - 156

SP - 397

EP - 405

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 3

ER -

Open problems around exact algorithms

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit