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
Version:
Publisher's version

Actions


Access Document


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

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
More from this funder
Funding agency for:
Santhanam, R
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik Publisher's website
Publication date:
2016-08-29
Acceptance date:
2016-06-09
DOI:
Pubs id:
pubs:647891
URN:
uri:fedc4ada-8103-49fb-879c-021210c9d196
UUID:
uuid:fedc4ada-8103-49fb-879c-021210c9d196
Local pid:
pubs:647891

Terms of use


Metrics


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