|
Size: 6497
Comment: added submission 35
|
← Revision 13 as of 2011-01-18 15:07:59 ⇥
Size: 6541
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| ||2||Reachability||Giorgio Terracina||Yes||Yes||Query||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Reachability#preview|view]]|| | ||2||Reachability||Giorgio Terracina||Yes||Yes||Query||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/Reachability|view]]|| |
| Line 37: | Line 37: |
| ||30||Hydraulic Leaking||Francesco Calimeri||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HydraulicLeaking|view]]|| ||31||Hydraulic Planning||Francesco Calimeri||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HydraulicPlanning|view]]|| |
||30||Hydraulic Leaking||Francesco Calimeri and Maria Carmela Santoro||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HydraulicLeaking|view]]|| ||31||Hydraulic Planning||Francesco Calimeri and Maria Carmela Santoro||Yes||Yes||Search||P||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/HydraulicPlanning|view]]|| |
Preliminary List of Selected Benchmark Problems
# |
Problem Name |
Author(s) |
Model & Solve Competition |
System Competition |
Type |
Class |
Language for System Competition |
Preliminary Problem Description |
1 |
Crossing minimization in layered graphs |
Peter Stuckey and Graeme Gange |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
2 |
Reachability |
Giorgio Terracina |
Yes |
Yes |
Query |
P |
ASP-Core |
|
3 |
Strategic Companies |
Mario Alviano, Marco Maratea and Francesco Ricca |
Yes |
Yes |
Search |
Beyond NP |
ASP-Core |
|
4 |
Company Controls |
Mario Alviano |
Yes |
Yes |
Optimization |
P |
ASP-RfC |
|
5 |
Company Controls Optimize |
Mario Alviano |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
6 |
Grammar-Based Information Extraction |
Marco Manna |
Yes |
Yes |
Search |
P |
ASP-Core |
|
7 |
Generalized Slitherlink |
Wolfgang Faber |
Yes |
No |
Search |
NP |
- |
|
8 |
Fastfood Optimality Check |
Wolfgang Faber |
Yes |
No |
Search |
NP |
- |
|
9 |
Fastfood Optimization |
Wolfgang Faber |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
10 |
Sokoban Decision |
Wolfgang Faber |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
11 |
Sokoban Optimization |
Wolfgang Faber |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
12 |
Knight Tour |
Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
13 |
Disjunctive Scheduling |
Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
14 |
Packing Problem |
Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
15 |
Tomography Problem |
Neng-Fa Zhou |
Yes |
Yes |
Optimization |
NP |
ASP-Core |
|
16 |
Maximal Clique |
Johan Wittocx |
Yes |
No |
Optimization |
Beyond NP/Opt |
- |
|
17 |
Labyrinth |
Martin Gebser |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
18 |
Minimal Diagnosis |
Martin Gebser |
Yes |
Yes |
Search |
Beyond NP |
ASP-Core |
|
19 |
Multi Context System Querying |
Peter Schüller |
No |
Yes |
Query |
NP |
ASP-Core |
|
20 |
Numberlink |
Naoyuki Tamura and Neng-Fa Zhou |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
21a |
Reverse Folding |
Andrea Formisano, Agostino Dovier and Enrico Pontelli |
Yes |
No |
Search |
NP |
- |
|
21b |
Gas Diffusion |
Andrea Formisano, Agostino Dovier and Enrico Pontelli |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
21c |
Tangram |
Andrea Formisano, Agostino Dovier and Enrico Pontelli |
Yes |
No |
Search |
NP |
- |
|
22 |
Hanoi Tower |
Miroslaw Truszczynski |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
23 |
Magic Square Sets |
Yisong Wang and Jia-Huai You |
Yes |
No |
Search |
NP |
ASP-RfC |
|
24 |
Airport Pickup |
A. Ricardo Morales |
Yes |
No |
Search |
NP |
- |
|
25 |
Graph Colouring |
Yuliya Lierler and Marcello Balduccini |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
26 |
Solitaire |
Yuliya Lierler and Marcello Balduccini |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
27 |
Partner Units |
Anna Ryabokon, Andreas Falkner and Gerhard Friedrich |
Yes |
No |
Search |
NP |
- |
|
27b |
Partner Units - Polynomial |
Anna Ryabokon, Andreas Falkner and Gerhard Friedrich |
Yes |
Yes |
Search |
P |
ASP-Core |
|
28 |
Weight-Assignment Tree |
Yuliya Lierler |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
30 |
Hydraulic Leaking |
Francesco Calimeri and Maria Carmela Santoro |
Yes |
Yes |
Search |
P |
ASP-Core |
|
31 |
Hydraulic Planning |
Francesco Calimeri and Maria Carmela Santoro |
Yes |
Yes |
Search |
P |
ASP-Core |
|
32 |
Stable Marriage problem |
Francesco Ricca |
Yes |
Yes |
Search |
P |
ASP-Core |
|
33 |
Maze Generation |
Martin Brain and Mario Alviano |
Yes |
Yes |
Search |
NP |
ASP-Core |
|
35 |
Incremental Scheduling |
Marcello Balduccini and Yuliya Lierler |
Yes |
Yes |
Search |
NP |
ASP-Core |