Concept
Assignment problem
Related publications (100)
A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem
We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...
Piscataway2024Certification of Bottleneck Task Assignment With Shortest Path Criteria
Maryam Kamgarpour, Tony Alan Wood
Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...
2023A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling
In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...
2023Optimal Task Assignment and Collision Avoidance for Mobile Robots
This report serves as a general overview of the semester project conducted in the SYCAMORE lab during the Spring 2022 semester. It focuses on multi- agent optimal task assignment methods, which have been implemented on state of the art simulation methods u ...
2022Spectral Hypergraph Sparsifiers of Nearly Linear Size
Mikhail Kapralov, Jakab Tardos
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...
IEEE COMPUTER SOC2022Modeling congestion in a competitive Facility Location Problem
Assigning the right Emergency Room (ER) to persons in medical need is a pivotal mission of the Emergency Medical Dispatcher (EMD). In order to minimize the delay between the call and the medical care, EMD need to take into account the travel time and the w ...
2022A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness
Solving the Lexicographic Bottleneck Assignment Problem (LexBAP) typically relies on centralised computation with order complexity. We consider the Sequential Bottleneck Assignment Problem (SeqBAP), which yields a greedy solution to the LexBAP and discuss ...
Elsevier2022Large-scale traffic signal control and multimodal network design
Traffic congestion constitutes one of the most frequent, yet challenging, problems to address in the urban space. Caused by the concentration of population, whose mobility needs surpass the serving capacity of urban networks, congestion cannot be resolved ...
EPFL2022Discrete Optimal Transport with Independent Marginals is #P-Hard
Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen
We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...
2022