Matroid Polytopes: Algorithms, Theory, and Applications

Details Matroid Polytopes: Algorithms, Theory, and Applications Matroid Polytopes: Algorithms, Theory, and Applications

2009-05-27

arxiv.org/abs/0905.4405v1

Mathematics

Combinatorics

Scientific paper

This dissertation presents new results on three different themes all related to matroid polytopes. First we investigate properties of Ehrhart polynomials of matroid polytopes, independence matroid polytopes, and polymatroids. We prove that for fixed rank their Ehrhart polynomials are computable in polynomial time. The proof relies on the geometry of these polytopes as well as a new refined analysis of the evaluation of Todd polynomials. Second, we discuss theoretical results regarding the algebraic combinatorics of matroid polytopes. We discuss two conjectures about the h^*-vector and coefficients of Ehrhart polynomials of matroid polytopes and provide theoretical and computational evidence for their validity. We also explore a variant of White's conjecture which states that every matroid polytope has a regular unimodular triangulation. We provide extensive computational evidence supporting this new conjecture and propose a combinatorial condition on simplices sufficient for unimodularity. Finally, motivated by recent work on algorithmic theory for non-linear and multicriteria matroid optimization, we have developed algorithms and heuristics aimed at practical solutions of large instances of these difficult problems. Our methods primarily use the local adjacency structure inherent in matroid polytopes to pivot to feasible solutions which may or may not be optimal. We also present a modified breadth-first-search heuristic that uses adjacency to enumerate a subset of feasible solutions. We present other heuristics, and provide computational evidence supporting these new techniques. We implemented all of our algorithms in the software package MOCHA (Matroids Optimization Combinatorial Heuristics and Algorithms).

Affiliated with

Also associated with

No associations

Rating

Matroid Polytopes: Algorithms, Theory, and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Matroid Polytopes: Algorithms, Theory, and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matroid Polytopes: Algorithms, Theory, and Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527666