research
∙
07/21/2023
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Despite extensive research on distance oracles, there are still large ga...
share
research
∙
06/15/2023
On the Giant Component of Geometric Inhomogeneous Random Graphs
In this paper we study the threshold model of geometric inhomogeneous ra...
research
∙
05/29/2023
Analysis of the (1+1) EA on LeadingOnes with Constraints
Understanding how evolutionary algorithms perform on constrained problem...
research
∙
05/19/2023
Approximate Distance Sensitivity Oracles in Subquadratic Space
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
05/19/2023
Evolutionary Diversity Optimisation in Constructing Satisfying Assignments
Computing diverse solutions for a given problem, in particular evolution...
research
∙
05/12/2023
Temporal Network Creation Games
Most networks are not static objects, but instead they change over time....
research
∙
05/05/2023
Fault-Tolerant ST-Diameter Oracles
We study the problem of estimating the ST-diameter of a graph that is su...
research
∙
04/27/2023
Compact Distance Oracles with Large Sensitivity and Low Stretch
An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch ...
research
∙
02/23/2023
Single-Peaked Jump Schelling Games
Schelling games model the wide-spread phenomenon of residential segregat...
research
∙
02/22/2023
Fair Correlation Clustering in Forests
The study of algorithmic fairness received growing attention recently. T...
research
∙
02/13/2023
A simple statistic for determining the dimensionality of complex networks
Detecting the dimensionality of graphs is a central topic in machine lea...
research
∙
02/08/2023
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
A recent trend in the context of graph theory is to bring theoretical an...
research
∙
11/24/2022
Theoretical Study of Optimizing Rugged Landscapes with the cGA
Estimation of distribution algorithms (EDAs) provide a distribution - ba...
research
∙
11/11/2022
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
We prove an approximate max-multiflow min-multicut theorem for bounded t...
research
∙
11/02/2022
Deep Distance Sensitivity Oracles
One of the most fundamental graph problems is finding a shortest path fr...
research
∙
07/19/2022
Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
In the 1970s, Győri and Lovász showed that for a k-connected n-vertex gr...
research
∙
07/08/2022
The Impact of Cooperation in Bilateral Network Creation
Many real-world networks, like the Internet, are not the result of centr...
research
∙
04/22/2022
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
We construct data structures for extremal and pairwise distances in dire...
research
∙
04/21/2022
Social Distancing Network Creation
During a pandemic people have to find a trade-off between meeting others...
research
∙
04/04/2022
Using random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials
We study computational aspects of Gibbs point processes that are defined...
research
∙
02/28/2022
Fast Feature Selection with Fairness Constraints
We study the fundamental problem of selecting optimal features for model...
research
∙
01/25/2022
What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization
Combinatorial optimization lies at the core of many real-world problems....
research
∙
12/06/2021
Fixed-Parameter Sensitivity Oracles
We combine ideas from distance sensitivity oracles (DSOs) and fixed-para...
research
∙
12/05/2021
Computing Voronoi Diagrams in the Polar-Coordinate Model of the Hyperbolic Plane
A Voronoi diagram is a basic geometric structure that partitions the spa...
research
∙
10/22/2021
An Efficient Branch-and-Bound Solver for Hitting Set
The hitting set problem asks for a collection of sets over a universe U ...
research
∙
10/11/2021
Towards Explainable Real Estate Valuation via Evolutionary Algorithms
Human lives are increasingly influenced by algorithms, which therefore n...
research
∙
07/19/2021
Algorithms for general hard-constraint point processes via discretization
We study a general model for continuous spin systems with hard-core inte...
research
∙
07/12/2021
Routing in Strongly Hyperbolic Unit Disk Graphs
Greedy routing has been studied successfully on Euclidean unit disk grap...
research
∙
07/08/2021
Pareto optimal and popular house allocation with lower and upper quotas
In the house allocation problem with lower and upper quotas, we are give...
research
∙
07/07/2021
Space-Efficient Fault-Tolerant Diameter Oracles
We design f-edge fault-tolerant diameter oracles (f-FDOs). We preprocess...
research
∙
06/29/2021
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Given a graph with a source vertex s, the Single Source Replacement Path...
research
∙
04/23/2021
Efficiency and Stability in Euclidean Network Design
Network Design problems typically ask for a minimum cost sub-network fro...
research
∙
03/24/2021
The Complexity of Dependency Detection and Discovery in Relational Databases
Multi-column dependencies in relational databases come associated with t...
research
∙
02/19/2021
The Flip Schelling Process on Random Geometric and Erdös-Rényi Graphs
Schelling's classical segregation model gives a coherent explanation for...
research
∙
02/12/2021
Adaptive Sampling for Fast Constrained Maximization of Submodular Function
Several large-scale machine learning tasks, such as data summarization, ...
research
∙
12/11/2020
Selfish Creation of Social Networks
Understanding real-world networks has been a core research endeavor thro...
research
∙
11/09/2020
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
We study the problem of counting the number of homomorphisms from an inp...
research
∙
11/09/2020
Balanced Crown Decomposition for Connectivity Constraints
We introduce the balanced crown decomposition that captures the structur...
research
∙
10/06/2020
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Finding a minimum vertex cover in a network is a fundamental NP-complete...
research
∙
09/23/2020
Fair Tree Connection Games with Topology-Dependent Edge Cost
How do rational agents self-organize when trying to connect to a common ...
research
∙
09/21/2020
Efficiently Computing Maximum Flows in Scale-Free Networks
We study the maximum-flow/minimum-cut problem on scale-free networks, i....
research
∙
08/24/2020
A Strategic Routing Framework and Algorithms for Computing Alternative Paths
Traditional navigation services find the fastest route for a single driv...
research
∙
07/16/2020
Polymer Dynamics via Cliques: New Conditions for Approximations
Abstract polymer models are systems of weighted objects, called polymers...
research
∙
07/15/2020
timeXplain – A Framework for Explaining the Predictions of Time Series Classifiers
Modern time series classifiers display impressive predictive capabilitie...
research
∙
06/26/2020
Flow-Based Network Creation Games
Network Creation Games(NCGs) model the creation of decentralized communi...
research
∙
05/14/2020
Shortest Distances as Enumeration Problem
We investigate the single source shortest distance (SSSD) and all pairs ...
research
∙
04/15/2020
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Satisfiability is considered the canonical NP-complete problem and is us...
research
∙
11/15/2019
Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings
We study the problem of maximizing a non-monotone submodular function un...
research
∙
11/06/2019
From Symmetry to Asymmetry: Generalizing TSP Approximations by Parametrization
We generalize the tree doubling and Christofides algorithm, the two most...
research
∙
10/01/2019