Rozšířené Formulace
| Thesis title in Czech: | Rozšířené Formulace |
|---|---|
| Thesis title in English: | Extended Formulations |
| Key words: | Mnohostěny|Lineární programování|Kombinatorická optimalizace |
| English key words: | Polytopes|Linear Programming|Combinatorial Optimization |
| Academic year of topic announcement: | 2025/2026 |
| Thesis type: | dissertation |
| Thesis language: | |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | doc. Hans Raj Tiwary, M.Sc., Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 07.10.2025 |
| Date of assignment: | 07.10.2025 |
| Confirmed by Study dept. on: | 07.10.2025 |
| Guidelines |
| 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. |
| References |
| * 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. |