8 papers
Physics-Informed Mixed Integer Programming Methods for Optimal Patch Antennas
Ruben Hoeksma, Jesse van Rhijn, Marc Uetz +1
Antennas come in various shapes and sizes, as their performance characteristics are very much dependent on their exact shape. Coming up with a shape that matches desired design cha…
Non-periodic Fourier propagation algorithms for partial differential equations
Channa Hatharasinghe, Run Yan Teh, Jesse van Rhijn +2
Spectral methods for partial differential equations (PDEs) with non-periodic boundary conditions arising in computational physics often use polynomial expansions on non-uniform gri…
Complexity of Local Search for Euclidean Clustering Problems
Bodo Manthey, Nils Morawietz, Jesse van Rhijn +1
We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for -Means cluste…
Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
Bodo Manthey, Jesse van Rhijn
We analyze the running time of the Hartigan-Wong method, an old algorithm for the -means clustering problem. First, we construct an instance on the line on which the method can…
Approximation Ineffectiveness of a Tour-Untangling Heuristic
Bodo Manthey, Jesse van Rhijn
We analyze a tour-uncrossing heuristic for the Travelling Salesperson Problem, showing that its worst-case approximation ratio is and its average-case approximation ratio is…
Improved Smoothed Analysis of 2-Opt for the Euclidean TSP
Bodo Manthey, Jesse van Rhijn
The 2-opt heuristic is a simple local search heuristic for the Travelling Salesperson Problem (TSP). Although it usually performs well in practice, its worst-case running time is p…
Towards a Lower Bound for the Average Case Runtime of Simulated Annealing on TSP
Bodo Manthey, Jesse van Rhijn
We analyze simulated annealing (SA) for simple randomized instances of the Traveling Salesperson Problem. Our analysis shows that the theoretically optimal cooling schedule of Haje…
A midpoint projection algorithm for stochastic differential equations on manifolds
Ria Rushin Joseph, Jesse van Rhijn, Peter D. Drummond
Stochastic differential equations projected onto manifolds occur in physics, chemistry, biology, engineering, nanotechnology and optimization, with interdisciplinary applications.…