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.
In polyhedral studies of 0/1 polytopes two prominent problems exist. One is the vertex enumeration problem: Given a system of inequalities, enumerate its feasible 0/1 points. Another one is the convex hull problem: Given a set of 0/1 points in dimension d, ...
Virtual private network design in the hose model deals with the reservation of capacities in a weighted graph such that the terminals in this network can communicate with one another. Each terminal is equipped with an upper bound on the amount of traffic t ...
In this paper, we introduce the notion of a constrained Minkowski sumwhich for two (finite) point-sets P,Q R2 and a set of k inequalities Ax b is defined as the point-set (P Q)Ax b= x = p+q | P, q Q, Ax b. We show that typical subsequ ...
This mapping problem has to be solved in many application scenarios. In the automotive industry, for example, the implementation of car functions involves distributed task sets running on multiple electronic control units (ECU) with bus-based inter-task co ...
We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize the amplitude of the electrical current flowing through the diodes which has a direct impact on the lifetime of such a display. The opt ...
We consider the following problem: Given a rational matrix A∈Qm×n and a rational polyhedron Q⊆Rm+p, decide if for all vectors b∈Rm, for which there exists an integral z∈Zp suc ...
It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...
Abstraction techniques based on simulation relations have become an important and effective proof technique to avoid the infamous state space explosion problem. In the context of Markov chains, strong and weak simulation relations have been proposed ((B. J ...
We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...
We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. Modeling the proble ...
