Computing faces up to k dimensions of a Minkowski sum of polytopes

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

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

Hyperbolic lattices are a new type of synthetic materials based on regular tessellations in non-Euclidean spaces with constant negative curvature. While so far, there has been several theoretical investigations of hyperbolic topological media, experimental ...

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

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

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

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

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

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

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

The variational approach is a cornerstone of computational physics, considering both conventional and quantum computing computational platforms. The variational quantum eigensolver algorithm aims to prepare the ground state of a Hamiltonian exploiting para ...

This paper introduces a new method for solving the distributed AC power flow (PF) problem by further exploiting the problem formulation. We propose a new variant of the ALADIN algorithm devised specifically for this type of problem. This new variant is cha ...

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

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

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

Computing faces up to k dimensions of a Minkowski sum of polytopes

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

Adaptive projected variational quantum dynamics

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

Anomalous and Chern topological waves in hyperbolic networks

Gibbs sampling the posterior of neural networks

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

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

Better Trees for Santa Claus

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

Fairness and Explainability in Clustering Problems

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Bayesian reconstruction of memories stored in neural networks from their connectivity

Phenomenological theory of variational quantum ground-state preparation

Rapid Scalable Distributed Power Flow with Open-Source Implementation

Hybrid Flock - Formation Control Algorithms

Discrete Optimal Transport with Independent Marginals is #P-Hard

Minimum Cost Intervention Design for Causal Effect Identification