Conference item icon

Conference item

Exponential time paradigms through the polynomial time lens

Abstract:

We propose a general approach to modelling algorithmic paradigms for the exact solution of NP-hard problems. Our approach is based on polynomial time reductions to succinct versions of problems solvable in polynomial time. We use this viewpoint to explore and compare the power of paradigms such as branching and dynamic programming, and to shed light on the true complexity of various problems.


As one instantiation, we model branching using the notion of witness compression, i.e...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.ESA.2016.36

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Santhanam, R
Grant:
615075
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik Publisher's website
Journal:
24th Annual European Symposium on Algorithms Journal website
Host title:
24th Annual European Symposium on Algorithms (ESA 2016)
Publication date:
2016-08-01
Acceptance date:
2016-06-09
DOI:
Source identifiers:
647891
Keywords:
Pubs id:
pubs:647891
UUID:
uuid:fedc4ada-8103-49fb-879c-021210c9d196
Local pid:
pubs:647891
Deposit date:
2016-10-04

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP