Publications (14)
A quantum algorithm for solving 0-1 Knapsack problems
Sören Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski +3
Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the "Q…
How Low Can We Go? Minimizing Interaction Samples for Configurable Systems
Dominik Krupke, Ahmad Moradi, Michael Perk +5
Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality…
Provable Methods for Searching with an Imperfect Sensor
Nilanjan Chakraborty, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell +2
Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capab…
The Lawn Mowing Problem: From Algebra to Algorithms
Sándor P. Fekete, Dominik Krupke, Michael Perk +2
For a given polygonal region , the Lawn Mowing Problem (LMP) asks for a shortest tour that gets within Euclidean distance 1/2 of every point in ; this is equivalent to co…
Drone Air Traffic Control: Tracking a Set of Moving Objects with Minimal Power
Chek-Manh Loi, Michael Perk, Malte Hoffmann +1
A common sensing problem is to use a set of stationary tracking locations to monitor a collection of moving devices: Given objects that need to be tracked, each following its o…
Use case study: benchmarking quantum breadth-first search for maximum flow problems
Andreea-Iulia Lefterovici, Lara Lelakowski, Michael Perk
The maximum flow problem asks to find the largest possible flow from a source to a sink in a capacitated network. It arises frequently in scheduling, project selection, and as a co…
A quantum search method for quadratic and multidimensional knapsack problems
Sören Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski +5
Solving combinatorial optimization problems is a promising application area for quantum algorithms in real-world scenarios. In this work, we extend the "Quantum Tree Generator" (QT…
Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We consider a class of optimization problems that are fundamental to testing in modern configurable software systems, e.g., in automotive industries. In pairwise interaction sampli…
Multi-Covering a Point Set by Disks with Minimum Total Area
Mariem Guitouni, Chek-Manh Loi, Sándor P. Fekete +2
A common robotics sensing problem is to place sensors to robustly monitor a set of assets, where robustness is assured by requiring asset to be monitored by at least se…
Beyond asymptotic scaling: Comparing functional quantum linear solvers
Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti +3
Solving systems of linear equations is a key subroutine in many quantum algorithms. In the last 15 years, many quantum linear solvers (QLS) have been developed, competing to achiev…
Exact Algorithms for Minimum Dilation Triangulation
Sándor P. Fekete, Phillip Keldenich, Michael Perk
We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable…
A Closer Cut: Computing Near-Optimal Lawn Mowing Tours
Sándor P. Fekete, Dominik Krupke, Michael Perk +2
For a given polygonal region , the Lawn Mowing Problem (LMP) asks for a shortest tour that gets within Euclidean distance 1 of every point in ; this is equivalent to comp…
Realistic Runtime Analysis for Quantum Simplex Computation
Sabrina Ammann, Maximilian Hess, Debora Ramacciotti +10
In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic wors…
Computing Area-Optimal Simple Polygonizations
Sándor P. Fekete, Andreas Haas, Phillip Keldenich +2
We consider methods for finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set of points in the plane. Both problems are known to be NP-…