Dalle Molle Institute for Artificial Intelligence Research

The Dantzig–Fulkerson–Johnson TSP Formulation Is Easy to Solve for Few Subtour Constraints

The most successful approaches for the traveling salesman problem (TSP) use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relati...

A PTAS for triangle-free 2-matching

Abstract In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph $$G=(V,E)$$ G = ( V , E ) . Our goal is to compute a maximum-cardinality $$M\subseteq E$$ M ⊆ E satisfying the following properties: (1) at most two edges of M are incident on each node (i....

The Bidirected Cut Relaxation for Steiner Tree Has Integrality Gap Smaller than 2

Abstract. The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to compute a minimum-weight tree containing all terminals (and possibly further vertices...

Sleep-stage dynamics predict current sleep-disordered breathing and future cardiovascular risk

ABSTRACT Sleep-disordered breathing (SDB) is a major contributor to cardiovascular morbidity and disrupts both the macrostructure and dynamics of sleep stages (W, N1, N2, N3, REM). While specific alterations in sleep macrostructure, such as reduced durations of N3 and REM, have b...

A \({(2+\varepsilon )}\)-Approximation Algorithm for Metric \({k}\)-Median

Abstract. In the classical NP-hard (metric) [Formula: see text]-median problem, we are given a set of [Formula: see text] clients and centers with metric distances between them, along with an integer parameter [Formula: see text]. The objective is to select a subset of [Formula:...

dynoGP: Deep Gaussian Processes for Dynamic System Identification

ABSTRACT In this work, we present a novel approach to system identification for dynamical systems, based on a specific class of deep Gaussian processes (deepGPs). These models are constructed by interconnecting linear dynamic GPs (equivalent to stochastic linear time‐invariant dy...