Rozšířené Formulace
| Název práce v češtině: | Rozšířené Formulace |
|---|---|
| Název v anglickém jazyce: | Extended Formulations |
| Klíčová slova: | Mnohostěny|Lineární programování|Kombinatorická optimalizace |
| Klíčová slova anglicky: | Polytopes|Linear Programming|Combinatorial Optimization |
| Akademický rok vypsání: | 2025/2026 |
| Typ práce: | disertační práce |
| Jazyk práce: | |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | doc. Hans Raj Tiwary, M.Sc., Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 07.10.2025 |
| Datum zadání: | 07.10.2025 |
| Datum potvrzení stud. oddělením: | 07.10.2025 |
| Zásady pro vypracování |
| This thesis will explore "Extended Formulations" which refers to lifting polytopes to higher dimensions in order to reduce the number of inequalities needed to describe the polytope. It is frequently used in Linear Programming methods for Combinatorial Optimization but the techniques used to prove both lower and upper bounds for the size of extended formulations is rather limited. So the goal is to explore this area and come up with lower/upper bounds for specific polytopes as well as to find general methods that work for many polytopes. |
| Seznam odborné literatury |
| * Conforti, M., Cornuéjols, G., & Zambelli, G. (2013). Extended formulations in combinatorial optimization. Annals of Operations Research, 204(1), 97-143.
* Yannakakis, M. (1991). Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3), 441-466. * Fiorini, S., Massar, S., Pokutta, S., Tiwary, H., & de Wolf, R. (2012). Linear vs. semidefinite extended formulations: Exponential separation. Proceedings of the 44th ACM Symposium on Theory of Computing * Rothvoß, T. (2014). The matching polytope has exponential extension complexity. Journal of the ACM, 64(6), 1-19. |