welcome: please sign in
location: Diff for "PreliminaryProblemList"
Differences between revisions 9 and 10
Revision 9 as of 2011-01-10 16:24:33
Size: 6302
Comment: new accepted problem.
Revision 10 as of 2011-01-10 16:26:30
Size: 6303
Comment:
Deletions are marked like this. Additions are marked like this.
Line 32: Line 32:
||25||GraphColouring||Yuliya Lierler and Marcello Balduccini||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/GraphColouring|view]]|| ||25||Graph Colouring||Yuliya Lierler and Marcello Balduccini||Yes||Yes||Search||NP||ASP-Core||[[https://www.mat.unical.it/aspcomp2011/ProblemsDescription/GraphColouring|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

-

view

2

Reachability

Giorgio Terracina

Yes

Yes

Query

P

ASP-Core

view

3

Strategic Companies

Mario Alviano, Marco Maratea and Francesco Ricca

Yes

Yes

Search

Beyond NP

ASP-Core

view

4

Company Controls

Mario Alviano

Yes

Yes

Optimization

P

ASP-RfC

view

5

Company Controls Optimize

Mario Alviano

Yes

No

Optimization

Beyond NP/Opt

-

view

6

Grammar-Based Information Extraction

Marco Manna

Yes

Yes

Search

P

ASP-Core

view

7

Generalized Slitherlink

Wolfgang Faber

Yes

No

Search

NP

-

view

8

Fastfood Optimality Check

Wolfgang Faber

Yes

No

Search

NP

-

view

9

Fastfood Optimization

Wolfgang Faber

Yes

No

Optimization

Beyond NP/Opt

-

view

10

Sokoban Decision

Wolfgang Faber

Yes

Yes

Search

NP

ASP-Core

view

11

Sokoban Optimization

Wolfgang Faber

Yes

No

Optimization

Beyond NP/Opt

-

view

12

Knight Tour

Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

13

Disjunctive Scheduling

Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

14

Packing Problem

Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

15

Tomography Problem

Neng-Fa Zhou

Yes

Yes

Optimization

NP

ASP-Core

view

16

Maximal Clique

Johan Wittocx

Yes

No

Optimization

Beyond NP/Opt

-

view

17

Labyrinth

Martin Gebser

Yes

Yes

Search

NP

ASP-Core

view

18

Minimal Diagnosis

Martin Gebser

Yes

Yes

Search

Beyond NP

ASP-Core

view

19

Multi Context System Querying

Peter Schüller

No

Yes

Query

NP

ASP-Core

view

20

Numberlink

Naoyuki Tamura and Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

21a

Reverse Folding

Andrea Formisano, Agostino Dovier and Enrico Pontelli

Yes

No

Search

NP

-

view

21b

Gas Diffusion

Andrea Formisano, Agostino Dovier and Enrico Pontelli

Yes

Yes

Search

NP

ASP-Core

view

21c

Tangram

Andrea Formisano, Agostino Dovier and Enrico Pontelli

Yes

No

Search

NP

-

view

22

Hanoi Tower

Miroslaw Truszczynski

Yes

Yes

Search

NP

ASP-Core

view

23

Magic Square Sets

Yisong Wang and Jia-Huai You

Yes

No

Search

NP

ASP-RfC

view

24

Airport Pickup

A. Ricardo Morales

Yes

No

Search

NP

-

view

25

Graph Colouring

Yuliya Lierler and Marcello Balduccini

Yes

Yes

Search

NP

ASP-Core

view

26

Solitaire

Yuliya Lierler and Marcello Balduccini

Yes

Yes

Search

NP

ASP-Core

view

27

Partner Units

Anna Ryabokon, Andreas Falkner and Gerhard Friedrich

Yes

No

Search

NP

-

view

27b

Partner Units - Polynomial

Anna Ryabokon, Andreas Falkner and Gerhard Friedrich

Yes

Yes

Search

P

ASP-Core

view

28

Weight-Assignment Tree

Yuliya Lierler

Yes

Yes

Search

NP

ASP-Core

view

30

Hydraulic Leaking

Francesco Calimeri

Yes

Yes

Search

P

ASP-Core

view

31

Hydraulic Planning

Francesco Calimeri

Yes

Yes

Search

P

ASP-Core

view

32

Stable Marriage problem

Francesco Ricca

Yes

Yes

Search

P

ASP-Core

view

33

Maze Generation

Martin Brain and Mario Alviano

Yes

Yes

Search

NP

ASP-Core

view

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