Concept

Problème NP-complet

Publications associées (376)

MAP Estimation for Bayesian Mixture Models with Submodular Priors

Volkan Cevher, Luca Baldassarre, Marwa El Halabi

We propose a Bayesian approach where the signal structure can be represented by a mixture model with a submodular prior. We consider an observation model that leads to Lipschitz functions. Due to its combinatorial nature, computing the maximum a posteriori ...

2014

Picosecond acoustics method for measuring the thermodynamical properties of solids and liquids at high pressure and high temperature

Livia Eleonora Bove Kado

Based on the original combination of picosecond acoustics and diamond anvils cell, recent improvements to accurately measure hypersonic sound velocities of liquids and solids under extreme conditions are described. To illustrate the capability of this tech ...

Elsevier Science Bv2014

Salvage of the essential corrinoid cofactor in Dehalobacter restrictus

Christof Holliger, Julien Maillard, Yue Lu, Aamani Rupakula Boyanapalli, Sébastien Keller, Hauke Smidt

The corrinoid cofactor is essential for organohalide respiration (OHR), a bacterial metabolism assisting towards environmental depollution. Two different strategies for obtaining corrinoids, are used by OHR bacteria, either de novo biosynthesis or salvagin ...

2014

Single machine scheduling with scenarios

Ola Nils Anders Svensson

In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in ...

2013

On some coloring problems in grids

Dominique de Werra

We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...

2013

Buffer optimization based on critical path analysis of a dataflow program design

Marco Mattavelli, Simone Casale Brunet

The trade-off between throughput and memory constraints is a common design problem in embedded systems, and especially for streaming applications, where the memory in question usually occurs in the form of buffers for streams of data. This paper presents a ...

IEEE2013

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in ...

Springer Berlin Heidelberg2013

Tractability of interpretability via selection of group-sparse models

Volkan Cevher, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. A promise of these models is to lead to “interpretable” signals for which we identify i ...

2013

Decomposition and tractability in qualitative spatial and temporal reasoning

Jingshi Li

Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...

Elsevier2013

Randomized recovery for boolean compressed sensing

Martin Vetterli, Mitra Fatemi

We consider the problem of boolean compressed sensing, which is alternatively known as group testing. The goal is to recover a small number of defective items in a large set from a few collective binary tests. This problem can be formulated as a binary lin ...

2013

Graph Chatbot

Chattez avec Graph Search

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.

Connectez-vous pour utiliser Chat avec Graph Search