2 citations · 3 across the 3 of their papers we have counts for
5 papers · 1 filter
Capacitated Vehicle Routing in Graphic Metrics
Tobias Mömke, Hang Zhou
We study the capacitated vehicle routing problem in graphic metrics (graphic CVRP). Our main contribution is a new lower bound on the cost of an optimal solution. For graphic metri…
Breaking the Barrier of 2 for the Storage Allocation Problem
Tobias Mömke, Andreas Wiese
Packing problems are an important class of optimization problems. The probably most well-known problem if this type is knapsack and many generalizations of it have been studied in…
A QPTAS for Gapless MEC
Shilpa Garg, Tobias Mömke
We consider the problem Minimum Error Correction (MEC). A MEC instance is an n x m matrix M with entries from {0,1,-}. Feasible solutions are composed of two binary m-bit strings,…
A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics
Tobias Mömke
We show how to restrict the analysis of a class of online problems that includes the -server problem in finite metrics such that we only have to consider finite sequences of req…
Randomized online computation with high probability guarantees
Dennis Komm, Rastislav Královič, Richard Královič +1
We study the relationship between the competitive ratio and the tail distribution of randomized online minimization problems. To this end, we define a broad class of online problem…