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

Research output: Contribution to journal › Article › Academic › peer-review

61 Citations (Scopus)

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.

Original language	English
Pages (from-to)	397-405
Journal	Discrete Applied Mathematics
Volume	156
Issue number	3
DOIs	https://doi.org/10.1016/j.dam.2007.03.023
Publication status	Published - 2008

Access to Document

10.1016/j.dam.2007.03.023

Cite this

@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 B.V.",

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

SN - 0166-218X

VL - 156

SP - 397

EP - 405

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -

Open problems around exact algorithms

Abstract

Access to Document

Fingerprint

Cite this