A New Framework for Distributed Submodular Maximization

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.

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

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

Robots outside of the fenced factories have to deal with continuously changing environment, this requires fast and flexible modes of control. Planning methods or complex learning models can find optimal paths in complex surroundings, but they are computati ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

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

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

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

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

. High-resolution simulations of particle-based kinetic plasma models typically require a high number of particles and thus often become computationally intractable. This is exacerbated in multi-query simulations, where the problem depends on a set of para ...

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

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

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

Cycles are one of the fundamental subgraph patterns and being able to enumerate them in graphs enables important applications in a wide variety of fields, including finance, biology, chemistry, and network science. However, to enable cycle enumeration in r ...

Last-mile delivery in the logistics chain contributes to congestion in urban networks due to frequent stops. Crowd-shipping is a sustainable and low-cost alternative to traditional delivery but relies heavily on the availability of occasional couriers. In ...

Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, ...

Background: Although digital mobility outcomes (DMOs) can be readily calculated from real-world data collected with wearable devices and ad-hoc algorithms, technical validation is still required. The aim of this paper is to comparatively assess and validat ...

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

Control systems operating in real-world environments often face disturbances arising from measurement noise and model mismatch. These factors can significantly impact the perfor- mance and safety of the system. In this thesis, we aim to leverage data to de ...

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 New Framework for Distributed Submodular Maximization

Chat with Graph Search

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

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

Exact Obstacle Avoidance for Robots in Complex and Dynamic Environments Using Local Modulation

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Approximation Algorithms for Allocation and Network Design

Results on Sparse Integer Programming and Geometric Independent Sets

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Fairness and Explainability in Clustering Problems

Adaptive Symplectic Model Order Reduction Of Parametric Particle-Based Vlasov-Poisson Equation

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

Bayesian reconstruction of memories stored in neural networks from their connectivity

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

Formula Normalizations in Verification

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-constrained Cycles

A continuum approximation approach to the depot location problem in a crowd-shipping system

Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Assessing real-world gait with digital technology? Validation, insights and recommendations from the Mobilise-D consortium

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Data-Driven Control and Optimization under Noisy and Uncertain Conditions

Discrete Optimal Transport with Independent Marginals is #P-Hard