5 Works

A survey on graph problems parameterized above and below guaranteed values

Gregory Z. Gutin & Matthias Mnich
We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph G, a solution whose value is at least g(G)+k or at most g(G)−k, where g(G) is a guarantee on the value that any solution on G takes. The goal is to design algorithms which find such solution in time whose complexity in...

An asymptotic (4/3+epsilon)-approximation for the 2-dimensional vector bin packing problem

Ariel Kulik, Matthias Mnich & Hadas Shachnai
We study the 22-Dimensional Vector Bin Packing Problem (2VBP), a generalization of classic Bin Packing that is widely applicable in resource allocation and scheduling. In 2VBP we are given a set of items, where each item is associated with a two-dimensional volume vector. The objective is to partition the items into a minimal number of subsets (bins), such that the total volume of items in each subset is at most 11 in each dimension. We...

A scalable algorithm for shape optimization with geometric constraints in Banach spaces

Peter Marvin Müller, Jose Pinzón, Thomas Rung & Martin Siebenborn
This work develops an algorithm for PDE-constrained shape optimization based on Lipschitz transformations. Building on previous work in this field, the p-Laplace operator is utilized to approximate a descent method for Lipschitz shapes. In particular, it is shown how geometric constraints are algorithmically incorporated avoiding penalty terms by assigning them to the subproblem of finding a suitable descent direction. A special focus is placed on the scalability of the proposed methods for large scale parallel...

Application of p-Laplacian relaxed steepest descent to shape optimization in two-phase flows

Peter Marvin Müller, Martin Siebenborn & Thomas Rung
The paper is concerned with the minimal drag problem in shape optimization of merchant ships exposed to turbulent two-phase flows. Attention is directed to the solution of Reynolds Averaged Navier-Stokes equations using a Finite Volume method. Central aspects are the use of a p-Laplacian relaxed steepest descent direction and the introduction of crucial technical constraints to the optimization procedure, i.e. the center of buoyancy and the displacement of the underwater hull. The example included refers...

Efficient approximations for many-visits multiple traveling salesman problems

Kristóf Bérczi, Matthias Mnich & Roland Vincze
A fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of m salesmen jointly visit all cities from a set of n cities. The mTSP models many important real-life applications, in particular for vehicle routing problems. An extensive survey by Bektas (Omega 34(3), 2006) lists a variety of heuristic and exact solution procedures for the mTSP, which quickly solve particular problem instances. In this work we...

Registration Year

  • 2022

Resource Types

  • Preprint