Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

NP-difficile

Publications associées (29)

A Crowdsourced Gameplay for Whole-Genome Assembly via Short Reads

Kalpani Anuradha Welivita

Next-generation sequencing has revolutionized the field of genomics by producing accurate, rapid and cost-effective genome analysis with the use of high throughput sequencing technologies. This has intensified the need for accurate and performance efficien ...

2020

Adaptive Streaming in Interactive Multiview Video Systems

Pascal Frossard, Laura Toni, Xue Zhang

Multiview applications endow final users with the possibility to freely navigate within 3D scenes with minimum-delay. A real feeling of scene navigation is enabled by transmitting multiple high-quality camera views, which can be used to synthesize addition ...

2019

Modeling Superlattices of Dipolar and Polarizable Semiconducting Nanoparticles

Federico Giberti

We present an analytical model to describe the stability of arbitrary semiconducting nanoparticle (NP) superlattices as a function of the dipole and polarizability of their constituents. We first validate our model by comparison with density functional the ...

AMER CHEMICAL SOC2019

On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Konstantinos Balatsoukas Stimming, Aris Filos Ratsikas

In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes C of a given dimension k, for which t ...

IEEE2019

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

An Interactive Gameplay to Crowdsource Multiple Sequence Alignment of Genome Sequences: Genenigma

Kalpani Anuradha Welivita

Comparative genomics is a field of research that compares genomes of different organisms to identify common patterns. It is a powerful method used to identify the genetic diseases that cause mutations. Multiple Sequence Alignment (MSA) is an intermediate s ...

ASSOC COMPUTING MACHINERY2019

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

A Truthful, Privacy-Preserving, Approximately Efficient Combinatorial Auction For Single-minded Bidders

Boi Faltings, Sujit Prakash Gujar, Sankarshan Damle

Combinatorial auctions are widely used to sell resources/items. The challenges in such auctions are multi-fold. We need to ensure that bidders, the strategic agents, bid their valuations truthfully to the auction mechanism. Besides, the agents may desire p ...

ASSOC COMPUTING MACHINERY2019

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019