Tilbake til søkeresultatene

FRINATEK-Fri prosj.st. mat.,naturv.,tek

SCOPE - Exploiting Structure to Cope with Hard Problems

Tildelt: kr 12,5 mill.

En algoritme er en liste med presise instruksjoner for å løse en oppgave ved hjelp av en datamaskin. Mange av de mest interessante oppgavene vi vil løse med datamaskiner er så vanskelige at ingen har så langt klart å finne en rask og god algoritme for å løse dem. En god del av disse oppgavene kan modelleres ved hjelp av matematiske objekter kalt grafer. Dette prosjektet konsentrerer seg om vanskelige oppgaver som kan beskrives med grafer. Selv om mange av disse oppgavene er vanskelige i det generelle tilfellet, så vil de aller fleste tilfeller som dukker opp i praksis ha en viss struktur som gjør at vi klarer å utvikle raske algoritmer for løsningen av dem. Prosjektet studerer grafer med ulik struktur og finner gode algoritmer for vanskelige oppgaver når den gitte grafen har slik struktur. Prosjektets hovedmål har vært å identifisere grafer med ulik struktur der kjente vanskelige oppgaver kan løses med raske algoritmer. Vi har oppnådd dette målet på mange viktige oppgaver. Prosjektet har så langt publisert 68 artikler i internasjonale konferanser og 55 artikler i internasjonale tidsskrift.

Many problems that need to be solved in real-life computer science applications are very hard, in the sense that we do not have methods or hope to compute their optimal solutions efficiently. In this project we concentrate on input instances of these prob lems with particular structure, and exploit our knowledge on the structure to be able to give algorithms that are faster when the input has this structure. This not only allows us to handle these problems on structured input efficiently, but it also opens for the possibility of solving these problems within reasonable time and optimally on all types of input. The understanding for this comes from the tools that are in general applied to cope with hard problems. Two well-known methods in pursue of tractabi lity are reduction rules and branching rules. Reduction rules manage to get rid of the unimportant parts of the input efficiently. Branching rules manage to identify parts of the input on which we can do exhaustive search without spending too much time. A fter these rules are applied, we are often left with the remainder of the input which we need to deal with in some other way. In this case, if the remaining part has some particular structure and we know how to solve the problem efficiently on this type o f structure, then we are able to plug this knowledge in at this stage. This way we obtain algorithms that manage to solve the problem optimally on all inputs in running time that is reasonable for practical inputs. The focus of the project is thus to f ind efficient solution methods for hard problems on structured inputs. In particular we concentrate on problem areas that are related to computational biology, DNA mappings, phlogenetic trees, and linear algebra. We identify specific research challenges c oncerning graph algorithms for width parameters, linear layouts, clustering, sandwich problems, and perfect graphs. The solution of these challenges will immediately make important problems solvable in practice.

Budsjettformål:

FRINATEK-Fri prosj.st. mat.,naturv.,tek