Publications related to Strong LP formulations for scheduling splittable jobs on unrelated machines

Approximation Algorithms for Allocation and Network Design

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

EPFL2023

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

2022

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...

ASSOC COMPUTING MACHINERY2021

Vessel scheduling with pilotage and tugging considerations

Michel Bierlaire

This paper considers vessel scheduling with pilotage and tugging constraints in berthing operations with channel restrictions at seaports. To our knowledge, pilotage and tugging requirements have not been simultaneously considered in the literature. This w ...

PERGAMON-ELSEVIER SCIENCE LTD2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

How ageing shapes body and space representations: A comparison study between healthy young and older adults

Olaf Blanke, Andrea Serino, Michela Bassolino, Matteo Franza, Giuliana Sorrentino, Charlène Zuber

To efficiently interact with the external world, the brain needs to represent the size of the involved body parts - body representations (BR) - and the space around the body in which the interactions with the environment take place - peripersonal space rep ...

2020

Extremal Eigenvalues Of The Dirichlet Biharmonic Operator On Rectangles

We study the behaviour of extremal eigenvalues of the Dirichlet biharmonic operator over rectangles with a given fixed area. We begin by proving that the principal eigenvalue is minimal for a rectangle for which the ratio between the longest and the shorte ...

2020

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

Strong LP formulations for scheduling splittable jobs on unrelated machines

Graph Chatbot

Chat with Graph Search

Approximation Algorithms for Allocation and Network Design

Results on Sparse Integer Programming and Geometric Independent Sets

Streaming and Matching Problems with Submodular Functions

Discrete Optimal Transport with Independent Marginals is #P-Hard

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Vessel scheduling with pilotage and tugging considerations

New Results in Integer and Lattice Programming

How ageing shapes body and space representations: A comparison study between healthy young and older adults

Extremal Eigenvalues Of The Dirichlet Biharmonic Operator On Rectangles

New Graph Algorithms via Polyhedral Techniques

Streaming and Matching Problems with Submodular Functions

Approximation Algorithms for Allocation and Network Design

Results on Sparse Integer Programming and Geometric Independent Sets

Vessel scheduling with pilotage and tugging considerations

New Results in Integer and Lattice Programming

How ageing shapes body and space representations: A comparison study between healthy young and older adults

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Extremal Eigenvalues Of The Dirichlet Biharmonic Operator On Rectangles

New Graph Algorithms via Polyhedral Techniques

Discrete Optimal Transport with Independent Marginals is #P-Hard