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 Ltd2024Approximation Algorithms for Allocation and Network Design
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 ...
EPFL2023Tree in Tree: from Decision trees to Decision Graphs
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)2021Knapsack 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 Informatik2021Efficient 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 PRESS2020Scalable 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 ...
IEEE2020No 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 ...
INFORMS2019A 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 ...
2019The 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