Concept

Steiner tree problem

Related publications (102)

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Optimal containment control for a class of heterogeneous multi-agent systems with actuator faults

Ju Wu, Tong Wang

This article investigates the optimal containment control problem for a class of heterogeneous multi-agent systems with time-varying actuator faults and unmatched disturbances based on adaptive dynamic programming. Since there exist unknown input signals i ...

WILEY2023

Tree in Tree: from Decision trees to Decision Graphs

Mahsa Shoaran, Bingzhao Zhu

Decision trees have been widely used as classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), a framework that extends the conventional dec ...

Curran Associates, Inc, (NIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems)2021

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Efficient Allocations in Constant Time: Towards Scalable Solutions in the Era of Large Scale Intelligent Systems

Boi Faltings, Panayiotis Danassis

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the f ...

IOS PRESS2020

Scalable Learning-Based Sampling Optimization For Compressive Dynamic MRI

Volkan Cevher, Ruud van Heeswijk, Baran Gözcü, Armin Eftekhari, Thomas Sanchez

Compressed sensing applied to magnetic resonance imaging (MRI) allows to reduce the scanning time by enabling images to be reconstructed from highly undersampled data. In this paper, we tackle the problem of designing a sampling mask for an arbitrary recon ...

IEEE2020

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

The electric autonomous dial-a-ride problem

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provides shared-ride services to users specifying their origin, destination, and preferred arrival time. Typically, the problem consists of finding minimum cost routes, satisfying operational constraint ...

Elsevier2019

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.