國立虎尾科技大學 |

Transportation Networks and Matroids : = Algorithms through Circuits and Polyhedrality.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Transportation Networks and Matroids :/
Reminder of title:	Algorithms through Circuits and Polyhedrality.
Author:	Miller, Jacob Andrew.
Description:	1 online resource (128 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 78-04(E), Section: B.
Contained By:	Dissertation Abstracts International78-04B(E).
Subject:	Mathematics. -
Online resource:	click for full text (PQDT)
ISBN:	9781369202540

Transportation Networks and Matroids : = Algorithms through Circuits and Polyhedrality.
Miller, Jacob Andrew.

Transportation Networks and Matroids :Algorithms through Circuits and Polyhedrality. - 1 online resource (128 pages)

Source: Dissertation Abstracts International, Volume: 78-04(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

This thesis is concerned with problems on, and relating to, networks and matroids. We look at networks and matroids through their circuits and polyhedra, using these in several algorithmic ways for both theoretic and classification purposes.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9781369202540Subjects--Topical Terms:

527692
Mathematics.
Index Terms--Genre/Form:

554714
Electronic books.

Transportation Networks and Matroids : = Algorithms through Circuits and Polyhedrality.
LDR:03958ntm a2200385Ki 4500 001 909645
005 20180426091042.5
006 m o u
007 cr mn||||a|a||
008 190606s2016 xx obm 000 0 eng d
020 $a 9781369202540
035 $a (MiAaPQ)AAI10165878
035 $a (MiAaPQ)ucdavis:16200
035 $a AAI10165878
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Miller, Jacob Andrew. $3 1180525
245 1 0 $a Transportation Networks and Matroids : $b Algorithms through Circuits and Polyhedrality.
264 0 $c 2016
300 $a 1 online resource (128 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 78-04(E), Section: B.
500 $a Adviser: Jesus Antonio De Loera.
502 $a Thesis (Ph.D.) $c University of California, Davis $d 2016.
504 $a Includes bibliographical references
520 $a This thesis is concerned with problems on, and relating to, networks and matroids. We look at networks and matroids through their circuits and polyhedra, using these in several algorithmic ways for both theoretic and classification purposes.
520 $a First, we present work on the circuit diameters of transportation polytopes, those arising from transportation problems, a famous class of network-flow problems. These diameter concepts extend the traditional notion of polyhedral diameter using circuit augmentation steps. Utilizing algorithms with these augmentation steps, we place upper and lower bounds on some of these circuit diameters for transportation polytopes. This includes new Hirsch-sized bounds on the traditional diameter of transportation polytopes (referred to as the graph diameter), and its monotone version, in the cases of 2 x n and 3 x n transportation problems.
520 $a Second, we present work on some properties of discrete 2-Wasserstein barycenters. These are a type of discrete multi-marginal transportation problem, where one seeks an average of discrete probability measures. The resulting barycenter is solved via a linear program that closely resembles a network-flow problem, and in fact reduces to a transportation problem in the two measure case. Utilizing classic polyhedral and linear programming theory, we prove several properties of these barycenters. This includes exhibiting non-trivial optimal transports from the resulting barycenter to its defining measures, which were already known to exist in the continuous case. Further, we show a tight bound on the support of these barycenters and a fast strongly-polynomial time algorithm for the computation of discrete Wasserstein geodesics.
520 $a Finally, we present work on the weak-orientability and orientability of matroids. These are both properties on the circuits and cocircuits of matroids, and, in particular, are properties shared by all graphical matroids (i.e. matroids on networks). We introduce the Bland-Jensen linear system, a system of binary linear equations originally alluded to by R. G. Bland and D. L. Jensen for the detection of weak orientability. Then we extend these to non-linear systems for detecting orientability. Further, we utilize the original linear system for the detection of weak-orientability on all matroids with less than 9 elements and those of rank 3 with 10 to 12 elements. Lastly, we use these equation systems to discuss two possible minor-minimal families of non-weakly-orientable matroids: a new family that extends the Fano matroid and a recently rediscovered family by D. L. Jensen.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Mathematics. $3 527692
650 4 $a Applied mathematics. $3 1069907
655 7 $a Electronic books. $2 local $3 554714
690 $a 0405
690 $a 0364
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Davis. $b Mathematics. $3 1180526
773 0 $t Dissertation Abstracts International $g 78-04B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10165878 $z click for full text (PQDT)