Publications related to A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

Strengths and Limitations of Linear Programming Relaxations

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

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

Near-optimal Deployment of Dataflow Applications on Many-core Platforms with Real-time Guarantees

Alena Simalatsar, Stefanos Skalistis

Safe and optimal deployment of data-streaming applications on many-core platforms requires the realistic estimation of task Worst-Case Execution Time (WCET). On the other hand, task WCET depends on the deployment solution, due to the varying number of inte ...

IEEE2017

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

Strong LP formulations for scheduling splittable jobs on unrelated machines

Ola Nils Anders Svensson

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this ...

Springer Heidelberg2015

Local discontinuous Galerkin methods for fractional ordinary differential equations

Jan Sickmann Hesthaven

This paper discusses the upwinded local discontinuous Galerkin methods for the one-term/multi-term fractional ordinary differential equations (FODEs). The natural upwind choice of the numerical fluxes for the initial value problem for FODEs ensures stabili ...

2015

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

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

Sensing the real world

Juri Ranieri

A sensor is a device that detects or measures a physical property and records, indicates, or otherwise responds to it. In other words, a sensor allows us to interact with the surrounding environment, by measuring qualitatively or quantitatively a given phe ...

EPFL2014

Online Energy-Efficient Task-Graph Scheduling for Multicore Platforms

David Atienza Alonso, Karim Kanoun

Numerous Directed-Acyclic Graph (DAG) schedulers have been developed to improve the energy efficiency of various multi-core platforms. However, these schedulers make a priori assumptions about the relationship between the task dependencies, and they are un ...

Institute of Electrical and Electronics Engineers2014

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

Graph Chatbot

Chat with Graph Search

Strengths and Limitations of Linear Programming Relaxations

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

Near-optimal Deployment of Dataflow Applications on Many-core Platforms with Real-time Guarantees

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Strong LP formulations for scheduling splittable jobs on unrelated machines

Local discontinuous Galerkin methods for fractional ordinary differential equations

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Node-weighted network design and maximum sub-determinants

Sensing the real world

Online Energy-Efficient Task-Graph Scheduling for Multicore Platforms

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

Strong LP formulations for scheduling splittable jobs on unrelated machines

Node-weighted network design and maximum sub-determinants

Strengths and Limitations of Linear Programming Relaxations

Near-optimal Deployment of Dataflow Applications on Many-core Platforms with Real-time Guarantees

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Local discontinuous Galerkin methods for fractional ordinary differential equations

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Online Energy-Efficient Task-Graph Scheduling for Multicore Platforms

Sensing the real world