|
Polyhedra, Convex Geometry, and Optimization Workshop Tutorial & Talk Outlines
Tibor Szabo - (Tutorial) Unique Sink Orientation of Cubes (Motivation and Results): An orientation of the edge-graph of the n-dimensional hypercube is called a {\em unique sink orientation} if all subhypercubes have exactly one sink (a vertex incident to only incoming edges). In the vertex oracle model one would like to find the global sink by performing operations called {\em vertex evaluation}. In one vertex evaluation the oracle reveals the orientation of the edges incident to the queried vertex. The goal is to evaluate the global sink in as few evaluations as possible. As it turns out this model is the generalization of several optimization problems most notably linear programming and LCP on P-matrices. In the talks we will describe these relationships and discuss the (quite sparse) knowledge about algorithms. The talk includes works by Bernd Gaertner, Ingo Schurr and Emo Welzl.
-T. Szabo, E. Welzl, Unique Sink Orientations of Cubes, Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS) (2001) 547-555.
-I. Schurr, T. Szabo, Finding the Sink Takes Some Time, Discrete & Computational Geometry (2004), to appear. (An extended abstract appeared in Proc. 10th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2461 (2002) 833-844.)
Jon Lee - (Tutorial) In my first lecture, I will provide a tutorial on matroid and oriented matroid representation theory, culminating with two results: (i) a nice construction for realizing an orientation of a matroid that is represented over both GF(3) and GF(5), and (ii) a proof of a result (joint with Matt Scobee) that every orientation of a GF(3)-representable matroid can be realized by a "totally dyadic" matrix (over Q). This lecture provides the background and motivation for the lecture by Jakayla Robbins.References:
-J. Lee, European J. Combin., vol 20 (1999), no.8, 833--838.
- J. Lee and M. Scobee, J. Combin. Theory Ser. B, vol 77 (1999), no.2, 263--291.
In my second lecture, I will describe ongoing work concerning a non-standard polyhedral model for coloring problems. Part of this is joint work Francois Margot, part with Don Coppersmith, and part with Janny Leung and Sven de Vries. References:
- J. Lee, J. Comb. Optim. vol 6 (2002), no.3, 335--352.
- J. Lee, J. Leung and S. de Vries. Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation. IBM Research Report RC22303, January 2002. To appear in the Journal of Combinatorial Optimization.
- D. Coppersmith and J. Lee. Parsimonious binary-encoding in integer programming. IBM Research Report RC22838, July 2003.
- J. Lee and F. Margot. More on a binary-encoded coloring formulation, IBM Research Report RC22991, November 2003. To appear in In "Integer programming and combinatorial optimization (New York, 2004)", Lecture Notes in Computer Science. Springer, Berlin, 2004.Lee.
Francois Margot - (Talk) Isomorphism, Orthogonal Latin Squares and All-different Polytope: This talk discuss an ILP formulation based on the All-Different polytope for the generation of orthogonal Latin squares. It also describes a way to handle efficiently the symmetries in the formulation, both structural (permutation of rows/columns) and in the colors. These ideas can be used directly for other problems such as edge or vertex coloring of a graph. Joint work with Jon Lee.
Walter Morris Jr. - (Tutorial) LP-orientations of polytopal graphs: A graph is polytopal if its vertices and edges are the vertices and edges of a convex polytope. An orientation of the edges of a polytopal graph G is an LP-orientation if there is a polytope P and a linear function f so that G is the graph of P and the orientation of each edge e is the direction of increase of f on e. We will discuss the necessary condition of Holt and Klee and the sufficient condition of Klee and Mihalisin for LP-orientations. Recent work of Develin on LP-orientations of cubes and of Pfeifle and Ziegler on dual cyclic polytopes will be covered. Some ideas on using the parametric cost simplex method to generate necessary conditions for LP-orientations will be presented. If time permits, generalizations such as oriented matroid programming, unique sink orientations of cubes, and linear programming with no right hand side will be discussed.
-Holt, Klee, A proof of the strict monotone 4-step conjecture, Contemprary Mathematics 223, American Mathematical Society, 1999
-Mihalisin, Klee, Convex and linear orientations of polytopal graphs, Disc. Comp. Geom. 24 2000
-Develin, LP-orientations of cubes and cross-polytopes, to appear in Advances in Geometry
-Pfeifle, Ziegler, On the monotone upper bound problem, MG/0308186 to appear in Experimental Mathematics
Jakayla Robbins - (Tutorial) In an attempt to build on the work of Jon Lee and Matt Scobee, we begin to examine orientations of quaternary matroids, that is matroids that are representable over GF(4). Jim Geelen, James Oxley, Dirk Vertigan, and Geoff Whittle have shown that the class of matroids known as the free spikes are fundamental building blocks for quaternary matroids. Hence, we begin our search for nice results about the orientations of quaternary matroids by examining orientations of the free spikes. In my first lecture, I will introduce the free spikes and use the monotone boolean functions to construct all their orientations. In my second lecture, I will use this construction and the threshold functions to find an upper bound on the number of realizable orientations of the free spikes. If time permits, I will also discuss unique extensions of orientations.
Mike Develin - (Tutorial) Tropical Geometry: We will survey results in the emerging theory of geometry over the tropical semiring (R, min, +). This object has connections to algebraic geometry, algebraic statistics, combinatorial optimization, and phylogenetic trees. We will try to give a brief overview of all of these as well as some intrinsically interesting behavior of the tropical semiring.
-Tropical Convexity, M. Develin and B. Sturmfels, math.MG/0308254
-Tropical Halfspaces, M. Joswig, math.CO/0312068
-The space of n points on a tropical line in d-space, M. Develin, math.CO/0401224
-First steps in tropical geometry, J. Richter-Gebert, B. Sturmfels, and T. Theobald, math.AG/0306366
-The Tropical Grassmannian, D. Speyer and B. Sturmfels, math.AG/0304218
Komei Fukuda - (Talk) Old and new ideas of constructing non-representable OMs: We look at old and new ideas of constructing nonrepresentable oriented matroids. We start with the old idea of constructing a nondegenerate cyclying in oriented matroid programming. Our new ideas make use of the Holt-Klee condition for the LP-orientations in two ways, in the primal way and the dual way. One of the ways turns out to be quite useful and the other is still quite a mystery, i.e. the basic question as to whether it can be used to construct nonrepresentable OMs remains open. (Joint work with S. Moriyama and Y. Okamoto)
-F. Holt and V. Klee. A proof of the strict monotone {$4$}-step conjecture. In Advances in discrete and computational geometry (South Hadley, MA, 1996), volume 223 of Contemp. Math., pages 201--216. Amer. Math. Soc., Providence, RI, 1999.
Yoshio Okamoto - (Talk) The affine representation theorem for abstract convex geometries: An (abstract) convex geometry is a combinatorial abstract model introduced by Edelman & Jamison which captures a combinatorial essence of ``convexity'' shared by some structures including finite point sets, partially ordered sets, trees, rooted graphs. In this work, we introduce a generalized convex shelling, and we show that every convex geometry can be represented as a generalized convex shelling. This is ``the representation theorem for convex geometries'' similar to ``the representation theorem for oriented matroids'' by Folkman & Lawrence. An important feature is that our representation theorem is affine-geometric while that for oriented matroids is topological. Thus our representation theorem indicates the intrinsic simplicity of convex geometries and opens a new research direction in the theory of convex geometries. This is a joint work with Kenji Kashiwabara & Masataka Nakamura. Suggested readings: Preprint is available from my webpage. http://www.inf.ethz.ch/personal/okamotoy/
Andre Guerette - (Talk) On projections of hypermetric inequalities: In this talk, we will explore linear programming relaxations for the Max Cut problem in graphs. Specifically, we examine the polytope obtained by projecting homogeneous 3- and 5-gonal inequalities onto the edge sets of graphs. We will discuss a series of constructions to shed light on the complete linear description of such polytopes, in general. This involves the characterization of facets pertaining to edge subdivision expansion of k5 minors. Further, we discuss the relationship between the projection polytope and associated cut polytope for a graph and set a limit case on which they are equivalent (joint work with David Avis).
Daniel Soll - (Talk) A generalization of vertex-decomposeability: In my talk I want to present a 'maximum-property' of a shelling, which is a generalization of the concept of vertex decomposeability of simplicial complexes and implies a linear (in number of facets and dimension) bound on the diameter of the complex. We investigate the case of simplicial polytopes and give a dual description of a 'max-shelling'. We still do not know how large the class of 'max-shellable' polytopes is.
Bohdan Kaluzny - (Talk) Long admissible pivots paths on linear programs: All pivot rules for linear programming use admissible pivots of type I and/or of type II. In my talk I will present what is known to date, and current research into the bounds on the length of these admissible paths. In particular, I will discuss the maximal length path of the least-index criss-cross method for all n (#inequalities) and d (dimension). Using a deformed product of arrangements construction, we build examples where the criss-cross method visits nearly every vertex (order of n choose d) of the underlying hyperplane arrangement of the LP (joint work with K. Fukuda). |
|
