Polytope methods in parameterized complexity

点击翻译按钮获取中文摘要

Linear Programming is a mathematical problem-solving tool that has provenimmensely useful in industrial planning, operational research, and inmathematical optimisation more generally. Over the decades since itsinception, a deep and rich mathematical theory has developed around it,which has become a central part of the field of theoretical computerscience. The field has also spawned multiple commercial companies,including ILOG (now owned by IBM), who developed the CPLEX optimisationsuite, credited by IBM for improvements in business efficiency yieldingmultiple cases of savings of hundreds of millions of dollars.However, there is a disconnect between the theoretical and practicalstrands of this research. In theoretical computer science, the focus is onmethods with absolute guarantees of performance, i.e., performanceguarantees (in terms of efficiency of the algorithm and quality of theproduced solution) that apply for every possible input to the algorithm inquestion. Consequently, the set of algorithms considered is restricted tothose for which such "universal worst-case" guarantees are possible. Onthe other hand, methods employed in practice, such as branch-and-bound andbranch-and-cut, are known to have great success with many "real-world"instances, despite being highly inefficient in the rare worst case. Inother words, the coarse-grained problem view of theoretical computerscience leads to unnecessarily pessimistic conclusions.We propose a study of combinatorial optimisation, and in particular of thepower of linear programming tools and branch-and-bound-type methods, fromthe perspective of parameterized complexity. In parameterized complexity,the coarse-grained view described above is replaced by a morefine-grained, multivariate view of problem complexity, where thefeasibility of "easy" problem instances can be explained by some parameterof these instances being bounded, i.e., we can use a structural parameterto capture and quantify the relative instance difficulty.This perspective has recently had some success, where branch-and-boundalgorithms have been shown to have a very good theoretically guaranteedperformance for certain problems, under the assumption that the so-called"integrality gap" of these instances is bounded (a condition that is alsoknown to be relevant in practice). These results build upon some veryparticular structural properties of the linear programming-formulation ofthe problem, referred to as persistence and half-integrality -- propertiesthat have not previously been fully investigated by the theory community,possibly since their value is not apparent under a strict coarse-grainedworst case perspective.This project will investigate the conditions for such structuralproperties in several ways, thereby laying the foundations for a theory ofstructured problem relaxations, and using these tools to develop new anduseful algorithms for a range of important problems, both branch-and-boundbased and more traditional combinatorial ones.