Voting Tournaments and The Linear Ordering Polytope

Simple item page
dc.contributorSt. John, Audrey
dc.contributorSidman, Jessica
dc.contributor.advisorShepardson, Dylan
dc.contributor.authorBarkhuff, Grace
dc.date.accessioned2016-06-29T13:01:10Z
dc.date.available2016-06-29T13:01:10Z
dc.date.gradyear2016en_US
dc.date.issued2016-06-29
dc.description.abstractThis 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.en_US
dc.description.sponsorshipMathematics & Statisticsen_US
dc.identifier.urihttp://hdl.handle.net/10166/3902
dc.language.isoen_USen_US
dc.rights.restrictedrestricteden_US
dc.subjectmathen_US
dc.subjectpolyhedraen_US
dc.subjectlinear programmingen_US
dc.subjectoptimizationen_US
dc.subjectdiscrete mathen_US
dc.subjectgeometryen_US
dc.titleVoting Tournaments and The Linear Ordering Polytopeen_US
dc.typeThesis
mhc.degreeUndergraduateen_US
mhc.institutionMount Holyoke College

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
gBarkhuffThesis.pdf
Size:
749.99 KB
Format:
Adobe Portable Document Format
Download

Collections

Student Theses and Honors Collection