Seminar: Steven Miltenburg (VU) and Antonina Khramova (TU/e)

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Steven Miltenburg (VU)

Title: Complexity of fixed order routing

Abstract:

We consider the classic Vehicle Routing Problem with the additional property that all requests are ordered and the subtour of each server (or vehicle) must obey the fixed order. A scheduling version of this problem was introduced by Bosman et al. (2019). We study several metric spaces and objective functions and our results show that in some settings such a fixed order simplifies the problem, while in others it makes an easy problem become NP-hard. For general metrics, we show that c-capacitated VRP remains APX-hard in the fixed order setting for c = 3 and show that the well-known iterated tour partitioning algorithm yields a (2 − 1/c)-approximation. When all points are on the line, we show that the fixed order restriction makes VRP NP-hard to solve for minimizing total completion time or maximum completion time, in contrast to standard VRP.

The talk is based on joint work with René Sitters and Tim Oosterwijk.

Video:

Slides:

Speaker: Antonina Khramova (TU/e)

Title: A linear programming bound for sum-rank-metric codes

Abstract:

The sum-rank metric is a generalization of the well-known Hamming and rank metrics, where we consider tuples of matrices (possibly of different sizes) over a finite field, and the distance between two tuples is the sum of ranks of differences of respective entries of the tuple.

In this talk we use Delsarte's LP method to derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. The Delsarte's LP bound has been previously obtained for Hamming metric, rank metric, Lee metric, and others, but the sum-rank-metric case remained open. To derive the new LP bound, we propose a way to construct an association scheme for the sum-rank metric, since the approach used in the Hamming and the rank-metric cases fails due to the associated graph not being distance-regular in general.

Based on computational experiments on relatively small instances, we observe that the obtained bound outperforms all bounds previously known for sum-rank-metric codes.

The talk is based on joint work with Aida Abiad, Alexander L. Gavrilyuk, and Ilia Ponomarenko. The paper is available at: https://arxiv.org/abs/2406.15926


Video:

Slides: