The Parameterized Complexity of Cascading Portfolio Scheduling
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113727" target="_blank" >RIV/00216224:14330/19:00113727 - isvavai.cz</a>
Result on the web
<a href="http://papers.nips.cc/paper/8983-the-parameterized-complexity-of-cascading-portfolio-scheduling" target="_blank" >http://papers.nips.cc/paper/8983-the-parameterized-complexity-of-cascading-portfolio-scheduling</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
The Parameterized Complexity of Cascading Portfolio Scheduling
Original language description
Cascading portfolio scheduling is a static algorithm selection strategy which uses a sample of test instances to compute an optimal ordering (a cascading schedule) of a portfolio of available algorithms. The algorithms are then applied to each future instance according to this cascading schedule, until some algorithm in the schedule succeeds. Cascading algorithm scheduling has proven to be effective in several applications, including QBF solving and the generation of ImageNet classification models. It is known that the computation of an optimal cascading schedule in the offline phase is NP-hard. In this paper we study the parameterized complexity of this problem and establish its fixed-parameter tractability by utilizing structural properties of the success relation between algorithms and test instances. Our findings are significant as they reveal that in spite of the intractability of the problem in its general form, one can indeed exploit sparseness or density of the success relation to obtain non-trivial runtime guarantees for finding an optimal cascading schedule.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Advances in Neural Information Processing Systems 32 (NIPS 2019)
ISBN
9781728110448
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
7666-7676
Publisher name
Neural Information Processing Systems Foundation, Inc.
Place of publication
USA
Event location
Canada
Event date
Jan 1, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000534424307066