welcome: please sign in
location: Diff for "PreliminaryProblemList"
Differences between revisions 5 and 6
Revision 5 as of 2011-01-05 11:01:49
Size: 3304
Comment:
Revision 6 as of 2011-01-05 12:00:42
Size: 3313
Comment:
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
= List of Selected Benchmark Problems = = Preliminary List of Selected Benchmark Problems =
Line 7: Line 7:
|| # || '''Problem''' || '''Author(s)''' || '''Model & Solve track''' || '''System track''' || '''Language (sub)class''' || '''Type''' || '''Complexity''' ||
|| || || || ''(yes/no)'' || ''(yes/no)'' || ''(ASP-Core/ASP-RfC/Open)'' || ''(Search/Optimization/Query)'' || ''(P/NP/Beyond NP)'' || ''(Preliminary) Problem description'' || Accepted and available on the Competition Platform ||
|| # || '''Problem''' || '''Author(s)''' || '''Model & Solve track''' || '''System track''' || '''Language (sub)class''' || '''Type''' || '''Complexity''' || ''(Preliminary) Problem description'' || Accepted and available on the Competition Platform
|| || || || ''(yes/no)'' || ''(yes/no)'' || ''(ASP-Core/ASP-RfC/Open)'' || ''(Search/Optimization/Query)'' || ''(P/NP/Beyond NP)'' ||

UNDER CONSTRUCTION

Preliminary List of Selected Benchmark Problems


|| # || Problem || Author(s) || Model & Solve track || System track || Language (sub)class || Type || Complexity || (Preliminary) Problem description || Accepted and available on the Competition Platform || || || || (yes/no) || (yes/no) || (ASP-Core/ASP-RfC/Open) || (Search/Optimization/Query) || (P/NP/Beyond NP) ||

1

Crossing minimization in layered graphs

Stuckey

YES

NO

Open

Optimization

???

2

Reachability

Terracina

YES

YES

ASP-Core

Search

P

3

Strategic Companies

Alviano

YES

YES

ASP-Core

Search

Beyond NP

4

Company Controls

Alviano

YES

YES

ASP-RfC???

Optimization

P

5

Company Controls Optimize

Alviano

YES

NO

Open

Optimization

???

6

Grammar-Based Information Extraction

Manna

YES

YES

ASP-Core

Search

P

7

Generalized Slitherlink

Faber

YES

YES???

ASP-RfC???

Search

NP

8

Fastfood Optimality Check

Faber

YES

YES???

ASP-RfC???

Search

NP

9

Fastfood Optimization

Faber

YES

NO

Open

Optimization

???

10

Sokoban Decision

Faber

YES

YES

ASP-Core

Search

NP

11

Sokoban Optimization

Faber

YES

NO

Open

Optimization

???

12

Knight Tour

Neng-Fa Zhou

YES

YES

ASP-Core

Search

NP

13

Disjunctive Scheduling

Neng-Fa Zhou

YES

YES

ASP-Core

Search

NP

14

Packing Problem

Neng-Fa Zhou

YES

YES

ASP-Core

Search

NP

16

Maximal Clique

Wittocx

YES

NO

ASP-Core/ASP-RfC

Optimization

???

17

Labyrinth

Gebser

YES

YES

ASP-Core

Search

NP

18

Minimal Diagnosis

Gebser

YES

YES

ASP-Core

Beyond NP

19

Multi Context System Querying

Schueller

YES

YES

ASP-Core

Search

NP

20

Numberlink

Neng-Fa Zhou, Tamura

YES

???

ASP-Core

???

21a

Reverse Folding

Formisano, Dovier, Pontelli

YES

YES

ASP-Core

21b

Gas Diffusion

Formisano, Dovier, Pontelli

YES

YES???

Open

21c

Tangram

Formisano, Dovier, Pontelli

YES

YES???

Open

22

Hanoi Tower

Truszczynski

YES

YES

ASP-Core

Search

NP

23

Magic Square Sets

You

YES

YES???

ASP-RfC

Search

NP???

25

Graph Colouring

Lierler, Balduccini

YES

YES

ASP-Core

Search

NP

26

Solitaire

Lierler, Balduccini

YES

YES???

ASP-Core

Search

NP

27

Partner Units

Friedrich

YES

YES

ASP-RFC???

Search

NP

27b

Partner Units - Polynomial

Friedrich

YES

ASP-Core

Search

P

28

Weight-Assignment Tree

Lierler

YES

NO

ASP-Core

Search

NP

30

Hydraulic Leaking

Calimeri

NO

YES

ASP-Core

Search

P

31

Hydraulic Planning

Calimeri

NO

YES

ASP-Core

Search

P

32

Stable Marriage Problem

Ricca

ASP-Core

P

ASP Competition 2011: PreliminaryProblemList (last edited 2011-01-18 15:07:59 by CarmenSantoro)