Research check type A:Extended formulations from an algorithmic perspective
A selection announcement has been published to award n.1 research grant for the research project entitled “Extended formulations from an algorithmic perspective” to be conducted at the Department of Mathematics “Tullio Levi-Civita” under the supervision of Professor Marco Di Summa, who is the Research Project Supervisor.
The research grant, which shall have a duration of 24 months and be for a gross amount for the grant holder of 19.367,00 per annum, is issued in accordance with the current Regulations Governing Research Grant Awards pursuant to Art. 22 of Law no. 240/2010 for the aforementioned research project, in University Scientific Area no. 01 Mathematical Sciences and Scientific Sector and Discipline MAT/09 - Operational research.
The purpose of this research grant, which is funded by Project Assegni SID 2019 on “Extended formulations from an algorithmic perspective” of Professor Marco Di Summa and by the Departmental Development project Year: 2018 - 2022 "neXt - Networking the eXcellence in Mathematics and Computer Science", is to understand the extension complexity of some fundamental polyhedra in combinatorial optimization from a structural and algorithmic point of view. In particular, some problems that will be investigated include: improving the upper and lower bounds on the extension complexity of these polytopes; finding conditions under which it is possible to efficiently provide an extended formulation, when its existence is theoretically guaranteed; obtaining algorithms to construct exact or approximate extended formulations for a wide class of polyhedra.