39 citations · 89 across the 25 of their papers we have counts for
5 papers · 1 filter
Optimal strategies for patrolling fences
Bernhard Haeupler, Fabian Kuhn, Anders Martinsson +2
A classical multi-agent fence patrolling problem asks: What is the maximum length of a line that agents with maximum speeds can patrol if each point on the…
The edge-statistics conjecture for
Anders Martinsson, Frank Mousset, Andreas Noever +1
Let and be positive integers. We prove that if , then in every large enough graph , the fraction of -vertex subsets that induce exac…
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Johannes Lengler, Anders Martinsson, Angelika Steger
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions are (s…
The "No Justice in the Universe" phenomenon: why honesty of effort may not be rewarded in tournaments
Peter Hegarty, Anders Martinsson, Edvin Wedin
In 2000 Allen Schwenk, using a well-known mathematical model of matchplay tournaments in which the probability of one player beating another in a single match is fixed for each pai…
Even flying cops should think ahead
Anders Martinsson, Florian Meier, Patrick Schnider +1
We study the entanglement game, which is a version of cops and robbers, on sparse graphs. While the minimum degree of a graph G is a lower bound for the number of cops needed to ca…