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.
The support of a vector is the number of nonzero components. We show that given an integral mxn matrix A, the integer linear optimization problem max {c(T) x : Ax = b, x >= 0, x is an element of Z(n)} has an optimal solution whose support is bounded by 2m log(2 root m parallel to Lambda parallel to(infinity)), where parallel to Lambda parallel to(infinity) is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent of the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.
Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis