Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI

Enumeration Complexity of Problems in P

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.7/8
Tel.: +49 331 5509-3917
E-Mail: Stefan.Neubert(at)hpi.de
Links: Homepage

Supervisor: Prof. Dr. Tobias Friedrich
Advisor: Dr. Katrin Casel

In complexity theory, we try to figure out, how fast we can solve a problem. We discuss both how fast an existing algorithm for a problem is as well as whether there are inherent limits to how fast an algorithm can possibly solve a problem. Usually, one analyzes how long it takes an algorithm to solve a given problem instance from receiving the input data until completing computation and producing the output data. In my research I attempt an even more precise analysis: When provided with the input data, how long does it take till the first part of the solution is done? When will the second, third, … part be completed?

Currently, we are working on enumerating solutions to scheduling problems.