72 citations · 119 across the 18 of their papers we have counts for
23 papers
Computing Enclosing Depth
Bernd Gärtner, Fatime Rasiti, Patrick Schnider
Enclosing depth is a recently introduced depth measure which gives a lower bound to many depth measures studied in the literature. So far, enclosing depth has only been studied fro…
Optimizing Symbol Visibility through Displacement
Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy +3
In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positi…
A Note on the Faces of the Dual Koch Arrangement
Bernd Gärtner, Manuel Wettstein
We analyze the faces of the dual Koch arrangement, which is the arrangement of lines obtained by projective duality from the Koch chain . In particular, we show that…
A New Combinatorial Property of Geometric Unique Sink Orientations
Yuan Gao, Bernd Gärtner, Jourdain Lamperski
A unique sink orientation (USO) is an orientation of the hypercube graph with the property that every face has a unique sink. A number of well-studied problems reduce in strongly p…
Majority Model on Random Regular Graphs
Bernd Gärtner, Ahad N. Zehmakan
Consider a graph and an initial random coloring where each vertex is blue with probability and red otherwise, independently from all other vertices. In ea…
Pseudo Unique Sink Orientations
Vitor Bosshard, Bernd Gärtner
A unique sink orientation (USO) is an orientation of the -dimensional cube graph (-cube) such that every face (subcube) has a unique sink. The number of unique sink orientati…
Screening Rules for Convex Problems
Anant Raj, Jakob Olbrich, Bernd Gärtner +2
We propose a new framework for deriving screening rules for convex optimization problems. Our approach covers a large class of constrained and penalized optimization formulations,…
The Niceness of Unique Sink Orientations
Bernd Gärtner, Antonis Thomas
Random Edge is the most natural randomized pivot rule for the simplex algorithm. Considerable progress has been made recently towards fully understanding its behavior. Back in 2001…
ARRIVAL: A zero-player graph game in NP coNP
Jérôme Dohrau, Bernd Gärtner, Manuel Kohler +2
Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a specia…
Formal Verification of Obstacle Avoidance and Navigation of Ground Robots
Stefan Mitsch, Khalil Ghorbal, David Vogelbacher +1
The safety of mobile robots in dynamic environments is predicated on making sure that they do not collide with obstacles. In support of such safety arguments, we analyze and formal…
Random Sampling with Removal
Kenneth L. Clarkson, Bernd Gärtner, Johannes Lengler +1
We study randomized algorithms for constrained optimization, in abstract frameworks that include, in strictly increasing generality: convex programming; LP-type problems; violator…
Efficient edge-skeleton computation for polytopes defined by oracles
Ioannis Z. Emiris, Vissarion Fisikopoulos, Bernd Gärtner
In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. an algorithm whose complexity depends polynomially on the inpu…
Combinatorial Redundancy Detection
Komei Fukuda, Bernd Gärtner, May Szedlák
The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by equality…
Stochastic continuum armed bandit problem of few linear parameters in high dimensions
Hemant Tyagi, Sebastian Stich, Bernd Gärtner
We consider a stochastic continuum armed bandit problem where the arms are indexed by the ball of radius in . The reward functions $r :B_{…
Large Shadows from Sparse Inequalities
Bernd Gärtner, Christian Helbling, Yoshiki Ota +1
The -dimensional Goldfarb cube is a polytope with the property that all its vertices appear on some \emph{shadow} of it (projection onto a 2-dimensional plane). The Goldfa…
Continuum armed bandit problem of few variables in high dimensions
Hemant Tyagi, Bernd Gärtner
We consider the stochastic and adversarial settings of continuum armed bandits where the arms are indexed by [0,1]^d. The reward functions r:[0,1]^d -> R are assumed to intrinsical…
Variable Metric Random Pursuit
Sebastian U. Stich, Christian L. Müller, Bernd Gärtner
We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and…
A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix Linear Complementarity Problem
Bernd Gärtner, Markus Sprecher
We give a polynomial-time dynamic programming algorithm for solving the linear complementarity problem with tridiagonal or, more generally, Hessenberg P-matrices. We briefly review…
Optimization of Convex Functions with Random Pursuit
Sebastian U. Stich, Christian L. Müller, Bernd Gärtner
We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the…
Counting Unique-Sink Orientations
Jan Foniok, Bernd Gärtner, Lorenz Klaus +1
Unique-sink orientations (USOs) are an abstract class of orientations of the n-cube graph. We consider some classes of USOs that are of interest in connection with the linear compl…
Optimal Lower Bounds for Projective List Update Algorithms
Christoph Ambuehl, Bernd Gaertner, Bernhard von Stengel
The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitiv…
An Exponential Lower Bound on the Complexity of Regularization Paths
Bernd Gärtner, Martin Jaggi, Clément Maria
For a variety of regularized optimization problems in machine learning, algorithms computing the entire solution path have been developed recently. Most of these methods are quadra…
Pivoting in Linear Complementarity: Two Polynomial-Time Cases
Jan Foniok, Komei Fukuda, Bernd Gärtner +1
We study the behavior of simple principal pivoting methods for the P-matrix linear complementarity problem (P-LCP). We solve an open problem of Morris by showing that Murty's least…