Campus Event Calendar
Event Entry
New for: D1, D2, D3, D4
What and Who
AND/OR networks and an open problem in the intersection of NP and coNP
Martin Skutella
Max-Planck-Institut für Informatik - AG 1
Talk
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 30 July 2003
13:30
45 Minutes
46.1 - MPII
021
Saarbrücken
Abstract
The intention of this talk is to present a problem with a very rare complexity status. The problem is known to be in the intersection of NP and coNP but no polynomial time algorithm has been found so far. This constitutes an attractive starting point for future research.
My motivation for this problem stems from an interesting application in scheduling: scheduling with so-called AND/OR precedence constraints. But it has also applications in many other fields like, e.g., 2-person games on graphs etc.
Contact
Martin Skutella
116
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
algorithms; complexity; AND/OR networks; scheduling