9th Combinatorial Algorithms Day

Session 1

Abstract:
The Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm is an iterative method for solving unconstrained optimization problems. BFGS can be seen as an approximation of Newton's method that does not need to evaluate the Hessian directly. Instead, the inverse of the Hessian matrix is approximated using low-rank updates in every iteration. Both the "optimization" and "approximation" components of this algorithm influence each other, which can lead to interesting coupling effects, for example acceleration.
Whist the acceleration of BFGS has been observed on many practical problems, it has resisted thorough theoretical analysis. Recent findings of Gower and Richtárik (2016) shed some new light on this problem. In this talk I will discuss some recent results.

Abstract:
Given a polygon representing a transportation network together with a point p in its interior, we aim to extend the network by inserting a line segment, called feed-link, which connects p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation of some point q on the boundary is the ratio between the length of the shortest path from p to q through the extended network, and their Euclidean distance. The utility of a feed-link is inversely proportional to the maximal dilation over all boundary points.
We give a linear time algorithm for computing the feed-link with the minimum overall dilation, thus improving upon the previously known algorithm of complexity O(n log n).
This is joint work with Marko Savić.

Abstract:
We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters, if the combinatorial embedding of the underlying abstract graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph.

Abstract:
Given a set O of objects in the plane (and in ℝ³), we study the problem of preprocessing O into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside a query range Q.
This is joint work with Mark de Berg and Joachim Gudmundsson, presented at WADS 2015.

Session 2

Abstract:
Cooperative matching games have drawn much interest partly because of the connection with bargaining solutions in the networking environment. However, it is not always guaranteed that a network under investigation gives rise to a stable bargaining outcome. To address this issue, we consider a modification process, called stabilization, that yields a network with stable outcomes, where the modification should be as small as possible. Therefore, the problem is cast to a combinatorial-optimization problem in a graph. Recently, the stabilization by edge removal was shown to be NP-hard. On the contrary, in this paper, we show that other possible ways of stabilization, namely, edge addition, vertex removal and vertex addition, are all polynomial-time solvable. Thus, we obtain a complete complexity-theoretic classification of the natural four variants of the network stabilization problem. We further study weighted variants and prove that the variants for edge addition and vertex removal are NP-hard.
This is joint work with Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, and Yusuke Kobayashi.

Abstract:
Oriented matroids encode the combinatorics of a real point configuration. In this talk, we will have a look at the combinatorics of a complex point configuration. We will examine so called "phirotopes", that is, complex oriented matroids. (Real) oriented matroids can be understood as a singularity of phirotopes. Nevertheless, the theory of phirotopes substantially differs from the one of oriented matroids. The realizability of phirotopes, for example, can be determined by evaluating a polynomial, whereas deciding the realizability of oriented matroids is known to be NP-hard. I will give a short introduction to phirotopes and illustrate why we are interested in them by highlighting some surprising properties.

Abstract:
Visualization and real-time interactive simulation play an important role both in mathematical research and in mathematical communication. The CindyJS Project aims at the development of a software platform and its mathematical foundation that allows a versatile and fast prototyping of mathematical experiments and visualizations which can be used for research and demonstration. The project attacks both the mathematical and the software related aspects of such a platform. In particular, the system should be usable as a flexible authoring system for providing mathematical content that can run in contemporary web browsers (including mobile devices), taking advantage of modern hardware and software technologies.
This talk will give an overview about the capabilities of the software and the challenges we are facing during its development.

Abstract:
We study the amortized number of combinatorial changes (edge insertions and removals) needed to update the structure of the 1-skeleton of a polyhedron defined as the intersection of a set of n halfspaces in ℝ³ as a new halfspace is added. To that effect, we define an abstract update operation for planar graphs that can be used to model the addition of new halfspaces to the polyhedron. Moreover, this operation can also be used to model the addition of a new site in several variants of Voronoi diagrams.
Using this abstraction, we show that the amortized number of edge insertions and removals needed to maintain the combinatorial structure of the polyhedron as a new halfspace (or a new site to the Voronoi diagram) is added is O(√n) amortized. A matching Ω(√n) combinatorial lower bound is shown for this abstract operation. These results provide the first evidence of the existence of an algorithm to incrementally construct the intersection of n halfspaces in sub-quadratic time. Indeed, we present an algorithm running in O(n^3/2 polylog n) time for the special case where the 1-skeleton of the polyhedron is always a tree.
This is join work with Sarah Allen, John Iacono and Stefan Langerman.