Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
We consider mixed-integer sets described by system of linear inequalities in which the constraint matrix A is totally unimodular; the right-hand side is arbitrary vector; and a subset of the variables is required to be integer. We show that the problem of ...
In this paper, we introduce the notion of a constrained Minkowski sum: for two (finite) point-sets P, Q subset of R-2 and a set of k inequalities Ax >= b, it is defined as the point-set (P circle plus Q)(Ax >= b) = {x = p + q vertical bar p is an element o ...
We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...
Springer2009
, ,
We give a rigorous account on the complexity landscape of an important real-time scheduling problem that occurs in the design of software-based aircraft control. The goal is to distribute tasks τi=(ci,pi) on a minimum number of identical machines a ...
Springer-Verlag2010
,
Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...
Elsevier2009
,
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 ...
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 investigate the diameter of a natural abstraction of the 1-skeleton of polyhedra. Although this abstraction is simpler than other abstractions that were previously studied in the literature, the best upper bounds on the diameter of polyhedra continue to ...
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 ...
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 ...
