BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Edward D. Kim

Edward D. Kim appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.OC

Catalog footprint

What is connected

10works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2016arXiv

Tail diameter upper bounds for polytopes and polyhedra

In 1992, Kalai and Kleitman proved a quasipolynomial upper bound on the diameters of convex polyhedra. Todd and Sukegawa-Kitahara proved tail-quasipolynomial bounds on the diameters of polyhedra. These tail bounds apply when the number of facets is greater than a certain function of the dimension. We prove tail-quasipolynomial bounds on the diameters of polytopes and normal simplicial complexes. We also prove tail-polynomial upper bounds on the diameters of polyhedra.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An improved upper bound on the diameters of subset partition graphs

In 1992, Kalai and Kleitman proved the first subexponential upper bound for the diameters of convex polyhedra. Eisenbrand et al. proved this bound holds for connected layer families, a novel approach to analyzing polytope diameters. Very recently, Todd improved the Kalai-Kleitman bound for polyhedra to $(n-d)^{1+\log_2d}$. In this note, we prove an analogous upper bound on the diameters of subset partition graphs satisfying a property related to the connectivity property of connected layer families.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Combinatorics and Geometry of Transportation Polytopes: An Update

A transportation polytope consists of all multidimensional arrays or tables of non-negative real numbers that satisfy certain sum conditions on subsets of the entries. They arise naturally in optimization and statistics, and also have interest for discrete mathematics because permutation matrices, latin squares, and magic squares appear naturally as lattice points of these polytopes. In this paper we survey advances on the understanding of the combinatorics and geometry of these polyhedra and include some recent unpublished results on the diameter of graphs of these polytopes. In particular, this is a thirty-year update on the status of a list of open questions last visited in the 1984 book by Yemelichev, Kovalev and Kravtsov and the 1986 survey paper of Vlach.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A note on the diameter of transportation polytopes with prescribed source degrees

Brightwell, van den Heuvel and Stougie proved that the diameter of an $m \times n$ transportation polytope is at most $8(m+n-2)$, a factor of eight away from the Hirsch Conjecture. This bound was improved to $3(m+n-1)$ by Hurkens. We investigate diameters for certain classes of transportation polytopes. Note: After the completion of this note, we discovered that the class of transportation polytopes studied in this note was already considered in Michel L. Balinski. On two special classes of transportation polytopes. Math. Programming Stud., 1:43-58, 1974. Michel L. Balinski and Fred J. Rispoli. Signature classes of transportation polytopes. Mathematical Programming, 60(2, Ser. A):127-144, 1993. These papers contain both refinements of our results and generalizations to more general classes of transportation problems. In view of these papers, this note will not be submitted for publication.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of polyhedra. Another variant has superlinear asymptotic diameter, and together with some combinatorial operations, gives a concrete approach for disproving the Linear Hirsch Conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method

This dissertation investigates the geometric combinatorics of convex polytopes and connections to the behavior of the simplex method for linear programming. We focus our attention on transportation polytopes, which are sets of all tables of non-negative real numbers satisfying certain summation conditions. Transportation problems are, in many ways, the simplest kind of linear programs and thus have a rich combinatorial structure. First, we give new results on the diameters of certain classes of transportation polytopes and their relation to the Hirsch Conjecture, which asserts that the diameter of every $d$-dimensional convex polytope with $n$ facets is bounded above by $n-d$. In particular, we prove a new quadratic upper bound on the diameter of $3$-way axial transportation polytopes defined by $1$-marginals. We also show that the Hirsch Conjecture holds for $p \times 2$ classical transportation polytopes, but that there are infinitely-many Hirsch-sharp classical transportation polytopes. Second, we present new results on subpolytopes of transportation polytopes. We investigate, for example, a non-regular triangulation of a subpolytope of the fourth Birkhoff polytope $B_4$. This implies the existence of non-regular triangulations of all Birkhoff polytopes $B_n$ for $n \geq 4$. We also study certain classes of network flow polytopes and prove new linear upper bounds for their diameters.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

An update on the Hirsch conjecture

The Hirsch conjecture was posed in 1957 in a letter from Warren M. Hirsch to George Dantzig. It states that the graph of a d-dimensional polytope with n facets cannot have diameter greater than n - d. Despite being one of the most fundamental, basic and old problems in polytope theory, what we know is quite scarce. Most notably, no polynomial upper bound is known for the diameters that are conjectured to be linear. In contrast, very few polytopes are known where the bound $n-d$ is attained. This paper collects known results and remarks both on the positive and on the negative side of the conjecture. Some proofs are included, but only those that we hope are accessible to a general mathematical audience without introducing too many technicalities.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Graphs of Transportation Polytopes

This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an $m\times n$ transportation polytope is a multiple of the greatest common divisor of $m$ and $n$.

0 citations0 reviewsNo code linkedOpen access