Publication

Strong LP formulations for scheduling splittable jobs on unrelated machines

Related publications (57)

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.

A Fast Symbolic Transformation Based Algorithm for Reversible Logic Synthesis

Mathias Soeken

We present a more concise formulation of the transformation based synthesis approach for reversible logic synthesis, which is one of the most prominent explicit ancilla-free synthesis approaches. Based on this formulation we devise a symbolic variant of th ...

Springer Int Publishing Ag2016

APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION

Ola Nils Anders Svensson

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + root 3 + epsilon, improving upon the decade-old ratio of 3 + epsilon. Our improved approximation ratio is achieved by exploiting the power of pseudo-app ...

Siam Publications2016

A totally unimodular view of structured sparsity

Volkan Cevher, Marwa El Halabi

This paper describes a simple framework for structured sparse recovery based on convex optimization. We show that many interesting structured sparsity models can be naturally represented by linear matrix inequalities on the support of the unknown parameter ...

2015

Towards Tight Lower Bounds for Scheduling Problems

Ashkan Norouzi Fard, Abbas Bazzi

We show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness resul ...

Springer Int Publishing Ag2015

Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

Ola Nils Anders Svensson

We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time b ...

Springer2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Chidambaram Annamalai

We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a ce ...

2014

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

Fast prediction and evaluation of gravitational waveforms using surrogate models

Jan Sickmann Hesthaven

We propose a solution to the problem of quickly and accurately predicting gravitational waveforms within any given physical model. The method is relevant for both real-time applications and in more traditional scenarios where the generation of waveforms us ...

American Physical Society2014

Tractability of interpretability via selection of group-sparse models

Volkan Cevher, 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. A promise of these models is to lead to “interpretable” signals for which we identify i ...

2013

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

. Then, we draw a connection to Goem ...

EPFL2014