A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

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.

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 ...

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

We propose an adaptive quantum algorithm to prepare accurate variational time evolved wave functions. The method is based on the projected variational quantum dynamics (pVQD) algorithm, that performs a global optimization with linear scaling in the number ...

In this paper, we study sampling from a posterior derived from a neural network. We propose a new probabilistic model consisting of adding noise at every pre- and post-activation in the network, arguing that the resulting posterior can be sampled using an ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

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 ...

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

The advent of comprehensive synaptic wiring diagrams of large neural circuits has created the field of connectomics and given rise to a number of open research questions. One such question is whether it is possible to reconstruct the information stored in ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...

Hydropower plants play a crucial role in the power system facing ambitious renewable energy targets. Due to their inherent controllability, they are well suited to provide flexibility to the grid. However, an increased flexibility provision leads to a prol ...

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

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 ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

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 ...

A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks

Chat with Graph Search

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

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Adaptive projected variational quantum dynamics

Gibbs sampling the posterior of neural networks

Results on Sparse Integer Programming and Geometric Independent Sets

Approximation Algorithms for Allocation and Network Design

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Bayesian reconstruction of memories stored in neural networks from their connectivity

Fairness and Explainability in Clustering Problems

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization

Better Trees for Santa Claus

Maximum Independent Set: Self-Training through Dynamic Programming

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Streaming and Matching Problems with Submodular Functions

Approximate CVPp in time 2(0.802n)

Hybrid Flock - Formation Control Algorithms

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Space-Efficient Representations of Graphs

Discrete Optimal Transport with Independent Marginals is #P-Hard