Voting Tournaments and The Linear Ordering Polytope

Date

2016-06-29

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This thesis explores a geometric structure called the linear ordering polytope. The linear ordering polytope, L^n, is the convex hull of a collection of vertices constructed from every permutation of a set of size n. Because the number of vertices of L^n grows quickly with the size of the ordering and because the combinatorics underlying their configuration is complex, the complete set of facets of the general linear ordering polytope is not known. We explore the facets of L^n by looking at a connection between the solutions of a class of linear programs based in voting theory and the facets of L^n. We begin with expository work in polyhedral theory, optimization, and voting theory, and finish with an explanation of the connection between the linear programs and L^n. Since the linear ordering polytope appears in a wide range of problems that arise in discrete optimization, this work has possible practical implications for the design of efficient algorithms.

Description

Keywords

math, polyhedra, linear programming, optimization, discrete math, geometry

Citation