Publication

Approximation Algorithms for Modern Multi-Processor Scheduling Problems

Related publications (119)

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.

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

A Real-Time Multi-Camera Depth Estimation ASIC with Custom On-Chip Embedded DRAM

Jonathan Emmanuel D Narinx

The capability to process high-resolution videos in real-time is becoming more important in a wide variety of applications such as autonomous vehicles, virtual reality or intelligent surveillance systems. The high-accuracy and complex video processing algo ...

EPFL2019

When Stuck, Flip a Coin

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Algorithms For Clustering Problems

Ashkan Norouzi Fard

Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...

EPFL2018

Delay-Power-Rate-Distortion Optimization of Video Representations for Dynamic Adaptive Streaming

Pascal Frossard, Laura Toni, Chenglin Li

Dynamic adaptive streaming addresses user heterogeneity by providing multiple encoded representations at different rates and/or resolutions for the same video content. For delay-sensitive applications, such as live streaming, there is however a stringent r ...

IEEE2018

On some problems related to 2-level polytopes

Manuel Francesco Aprile

In this thesis we investigate a number of problems related to 2-level polytopes, in particular from the point of view of the combinatorial structure and the extension complexity. 2-level polytopes were introduced as a generalization of stable set polytopes ...

EPFL2018

Hybrid, Job-Aware, and Preemptive Datacenter Scheduling

Pamela Isabel Delgado Borda

Scheduling in datacenters is an important, yet challenging problem. Datacenters are composed of a large number, typically tens of thousands, of commodity computers running a variety of data-parallel jobs. The role of the scheduler is to assign cluster reso ...

EPFL2018

Using Structural Properties for Integer Programs

Kim-Manuel Klein

Integer programs (IPs) are one of the fundamental tools used to solve combinatorial problems in theory and practice. Understanding the structure of solutions of IPs is thus helpful to argue about the existence of solutions with a certain simple structure, ...

SPRINGER INTERNATIONAL PUBLISHING AG2018

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