Publication

Content Search Through Comparisons

Related publications (34)

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.

The interval constrained 3-coloring problem

Laura Sanità

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-co ...

Springer Verlag2010

A note on the data-driven capacity of P2P networks

Pascal Frossard

We consider two capacity problems in P2P networks. In the first one, the nodes have an infinite amount of data to send and the goal is to optimally allocate their uplink bandwidths such that the demands of every peer in terms of receiving data rate are met ...

2009

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

Maximum independent sets of commuting and noninterfering inversions

Bernard Moret, Krister Swenson

Background: Given three signed permutations, an inversion median is a fourth permutation that minimizes the sum of the pairwise inversion distances between it and the three others. This problem is NP-hard as well as hard to approximate. Yet median-based ap ...

2009

Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability

A binary tanglegram is a pair (S, T) of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge ...

Springer2009

A branch and bound algorithm for disassembly scheduling with assembly product structure⋆

Paul Xirouchakis, Hwa-Joong Kim

This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning hor ...

2009

Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms

Martin Vetterli, Razvan Cristescu

We consider the problem of correlated data gathering by a network with a sink node and a tree based communication structure, where the goal is to minimize the total trans- mission cost of transporting the information collected by the nodes, to the sink nod ...

2006

Energy-efficient Broadcasting in All-wireless Networks

Jean-Pierre Hubaux, Christian Enz, Mario Cagalj

In all-wireless networks, minimizing energy consumption is crucial as in most cases the nodes are battery-operated. We focus on the problem of power-optimal broadcast, for which it is well known that the broadcast nature of radio transmissions can be explo ...

2005

New approaches for virtual private network design

Friedrich Eisenbrand

Virtual private network design is the following NP-hard problem. We are given a communication network, represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The ...

2005

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

In this paper, we consider the minimization of a relevant energy consumption related cost function in the context of sensor networks where correlated sources are generated at various sets of source nodes and have to be transmitted to some set of sink nodes ...

Springer Verlag2004