Publication

The poset scheduling problem

Related publications (44)

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 weighted stable matching problem

Linda Farczadi

We study the stable matching problem in non-bipartite graphs with incomplete but strict preference lists, where the edges have weights and the goal is to compute a stable matching of minimum or maximum weight. This problem is known to be NP-hard in general ...

2017

Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Viktor Kuncak, Mikaël Mayer, Jad Hamza

Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute t ...

2017

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

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, 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. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

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

Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks

Martin Vetterli, Patrick Thiran, Runwei Zhang

Energy efficiency of wireless sensor networks (WSNs) can be improved by moving base stations (BSs), as this scheme evenly distributes the communication load in the network. However, physically moving BSs is complicated and costly. In this paper, we propose ...

2015

Virtually Moving Base Stations for Energy Efficiency in Wireless Sensor Networks

Martin Vetterli, Patrick Thiran, Runwei Zhang

ACM New York2015

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

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