A Polyhedral Approach to Multicriteria Optimization

MAREČEK, Jakub. A Polyhedral Approach to Multicriteria Optimization. Brno: Masarykova Univerzita, 2006, 45 s.

Základní údaje

• Originální název: A Polyhedral Approach to Multicriteria Optimization
• Název česky: Polyedrální přístup k multikriteriální optimalizaci
• Autoři: MAREČEK, Jakub.
• Vydání: Brno, 45 s. 2006.
• Nakladatel: Masarykova Univerzita

Další údaje

• Typ výsledku: Odborná kniha
• Utajení: není předmětem státního či obchodního tajemství
• WWW: URL
• Organizační jednotka: Fakulta informatiky

Anotace

This report introduces a new approach to discrete optimization, based on the insights of polyhedral combinatorics, and compares it to approaches used in mathematical programming, computational geometry and database systems. It presents an algorithm based on the polyhedral approach solving the following linear discrete optimization problem: preprocess a set of points in three dimensions in a way that would make possible to return the point of the set maximizing a given linear objective function $f$ in polylogarithmic time. The proposed algorithm preprocesses $n$ points in time $\bigO(n^3)$ and answers queries in time $\bigO(\log n)$ in the worst case.

Anotace česky

Práce představuje nový přístup k diskrétní optimalizaci založený na geometrii mnohostěnů. Srovnává jej s vybranými dalšími přístupy matematického programování, počítačové grafiky a databázových systémů a ilustruje jej na řešení následujícího problému lineární diskrétní optimalizace: předzpracuj množinu bodů ve třech dimenzích tak, aby při zadání lineární účelové funkce $f$ bylo možné vybrat bod maximalizující $f$. Navržený algoritmus v čase $\bigO(n^3)$ připraví datovou strukturu, která umožňuje na dotazy odpovídat v čase $\bigO(\log n)$.