Beregningsorientert kombinatorisk optimering i satellittkommunikasjon og billedanalyse

Mange problemer i anvendt statistikk og moderne kommunikasjon er ev kombinatorisk art. Eksempler på viktige aktuelle anvendelser er segmenteringsproblemer i statistisk billedanalyse, ruting av trafikk i kommunikasjonsnettverk og oppsett av tidstabeller i satellittkommunikasjon. Slike problemer leder til kombinatoriske optimeringsproblemer som er beregningsmessig vanskelige. Kompleksiteten skyldes at variable skal være heltallige, og slike problemer kan oftest modelleres som lineære heltallsoptimeringspro blemer.Slike problemer kan studeres ut fra teknikker i kombinatorikk, lineær optimering og algoritmeteori. I prosjektet vil man studere en slik klasse av kombinatoriske optimeringsproblemer som stammer fra satellittkommunikasjon/billedanalyse.Prosjektetsm ål er å (i) analysere den matematiske strukturen i problemet, (ii) finne effektive approksumasjonsalgoritmer og (iii) utvikle raskest mulige eksakte algoritmer basert påkuttplanmetoder og lineær optimering.