Publications associées à Problème NP-complet

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.

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Nisheeth Vishnoi

We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n). © 2014 Soc ...

Society for Industrial and Applied Mathematics2014

Majority Logic Representation and Satisfiability

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

Majority logic is a powerful generalization of common AND/OR logic. Original two-level and multi-level logic networks can use majority operators as primitive connective, in place of AND/ORs. In such a way, Boolean functions have novel means for compact rep ...

2014

An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes

Bernard Moret, Yu Lin, Mingfu Shao

Computing the edit distance between two genomes is a basic problem in the study of genome evolution. The double-cut-and-join (DCJ) model has formed the basis for most algorithmic research on rearrangements over the last few years. The edit distance under t ...

Springer Verlag2014

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Anastasios Kyrillidis

Certain optimization problems in communication systems, such as limited-feedback constant-envelope beamforming or noncoherent M-ary phase-shift keying (MPSK) sequence detection, result in the maximization of a fixed-rank positive semidefinite quadratic for ...

Institute of Electrical and Electronics Engineers2014

Matrix Completion on Graphs

Pierre Vandergheynst, Michael Bronstein, Xavier Bresson, Vasilis Kalofolias

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Al- though the problem under the standard low rank assumption is NP-hard, Cande`s and Recht sho ...

2014

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Pascal Frossard

Multiview video refers to videos of the same dynamic 3-D scene captured simultaneously by multiple closely spaced cameras from different viewpoints. We study interactive streaming of pre-encoded multiview videos, where, at any time, a client can request an ...

Ieee-Inst Electrical Electronics Engineers Inc2014

Matrix Completion on Graphs

Pierre Vandergheynst, Michael Bronstein, Xavier Bresson, Vasilis Kalofolias

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Although the problem is NP-hard, Candes and Recht showed that it can be exactly relaxed if the ...

2014

Mixed Potentials for Planar Multilayered Structures Including Conductive Interfaces

Juan Ramon Mosig, Michael Mattes, Ioannis Koufogiannis

A complete and automatized strategy has been developed to derive the Vector and Scalar Potential Green’s Functions (GFs) of planar multilayered structures that include conductive sheets. The propagator matrix technique is enhanced to include conductive she ...

2014

Problème NP-complet

Graph Chatbot

Chattez avec Graph Search

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Majority Logic Representation and Satisfiability

Deciding Conditional Termination

An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Matrix Completion on Graphs

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

Matrix Completion on Graphs

Approximation algorithms for regret minimization in vehicle routing problems

Mixed Potentials for Planar Multilayered Structures Including Conductive Interfaces

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Coding Structure and Replication Optimization for Interactive Multiview Video Streaming

An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes

Majority Logic Representation and Satisfiability

Deciding Conditional Termination

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Matrix Completion on Graphs

Matrix Completion on Graphs

Approximation algorithms for regret minimization in vehicle routing problems

Mixed Potentials for Planar Multilayered Structures Including Conductive Interfaces