Publication

Maximum independent sets of commuting and noninterfering inversions

Related publications (42)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Optimal Software Patching Plan for PMUs

Jean-Yves Le Boudec, Ola Nils Anders Svensson, Teklemariam Tsegay Tesfay

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the ...

2017

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

Improved hardness results for unique shortest vector problem

Divesh Aggarwal

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique s ...

Elsevier2016

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Pascal Frossard

In free viewpoint video, a viewer can choose at will any camera angle or the so-called "virtual view" to observe a dynamic 3-D scene, enhancing his/her depth perception. The virtual view is synthesized using texture and depth videos of two anchor camera vi ...

2015

Refining Regulatory Networks through Phylogenetic Transfer of Information

Bernard Moret, Xiuwei Zhang

The experimental determination of transcriptional regulatory networks in the laboratory remains difficult and time-consuming, while computational methods to infer these networks provide only modest accuracy. The latter can be attributed partly to the limit ...

2012

A Metric for Phylogenetic Trees Based on Matching

Bernard Moret, Yu Lin, Vaibhav Rajan

Comparing two or more phylogenetic trees is a fundamental task in computational biology. The simplest outcome of such a comparison is a pairwise measure of similarity, dissimilarity, or distance. A large number of such measures have been proposed, but so f ...

2012

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We propose a new formulation of the index coding problem, where instead of demanding a specific message, clients are “pliable” and are happy to receive any one message they do not have. We prove that with this relaxation, although some instances of this pr ...

Ieee2012

The Truncated Tracial Moment Problem

Sabine Burgdorf

We present tracial analogs of the classical results of Curto and Fialkow on moment matrices. A sequence of real numbers indexed by words in noncommuting variables with values invariant under cyclic permutations of the indexes, is called a tracial sequence. ...

Theta Foundation2012