Scalable Algorithms for Problems in Large-Scale Combinatorial Structures

We study three problems in combinatorial optimization and computational geometry in the framework of Algorithm Engineering: solving Edge Orientations, maintaining a Dynamic Convex Hull and computing Hypergraph Matchings.

In an undirected graph, the Edge Orientation problem asks for an orientation of every edge, such that the maximum out-degree is minimized. This problem is studied in static and dynamic graphs, where edges are added and removed arbitrarily.
We propose novel proofs and engineering techniques for the static, dynamic-exact and dynamic-approximate tasks. We present a new path-based algorithm for the static exact case and the first exact dynamic algorithm, maintaining optimal orientations during the whole sequence of changes.
In the dynamic approximate case, we engineer a well-known algorithm by Chekuri et al. for lambda-fair orientations and provide its first practical implementation.
Our experiments show that we can speed up the static case by 6.59 times, have a 32 % faster algorithm in the dynamic exact case and speed-up computations by a factor of up to 112 in the dynamic approximate setting.

The Dynamic Convex Hull task is to maintain the set of points that form the smallest, convex hull of all current points. We study the insertion-only and fully dynamic case in the planar setting. In the latter, points can also be removed.
Besides folklore algorithms, we present an insert-only and a fully dynamic data structure based on the logarithmic method. Here, the point sets are kept in logarithmic increasing buckets. Queries are returned in log-squared time in the number of currently presented points.
We investigate the robustness of our and competing methods. Our methods are robust, even with non-general positions.
Experiments in the insertion-only setting, show that our algorithm scales well on instances with larger hulls, like circle data, while naïve methods work surprisingly well on real-world instances in both modes of updates. In the fully dynamic setting for hulls with polynomial many points or update-heavy scenarios, our new data structure is the preferred method.

A Hypergraph Matching is a subset of edges in a hypergraph such that only one edge is selected per vertex. Our algorithms for this problem operate in the (semi-)streaming and parallel model.
We prove approximation guarantees for these algorithms and show their memory and running time requirements.
The parallel algorithm runs in the CRCW PRAM model. We provide a work-optimal and general CREW version of it. Our semi-streaming method reduces memory consumption by 13 times on a large set of instances. The parallel algorithm, when deployed on a GPU, is up to 76 times faster than CPU methods.

These studies are driven by the Algorithm Engineering Cycle, where theoretical insights influence implementations. Driven by experiments, adjustments are made to the algorithms.
We evaluate all approaches on large-scale datasets experimentally against the state-of-the-art. Our results show the excellent scaling behavior of our new methods for all three problems on real-world and synthetic datasets.