Publications related to Data Exchange Problem with Helpers

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

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

On Polynomial Algorithms for Normalizing Formulas

Viktor Kuncak, Simon Guilloud, Mario Bucev

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

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

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

Distance to the nearest land/coastline (including small subantarctic islands) for the five-minute average cruise track of the Antarctic Circumnavigation Expedition (ACE) during the austral summer of 2016/2017.

Julia Schmale, Jenny Thomas, Sebastian Johannes Heinz-Josef Landwehr

Dataset abstract This dataset is derived from: - The GPS track of the R/V-Akademik Tryoshnikov (10.5281/zenodo.3772377) - The shapefiles of the continents from NaturalEarth physical (@50m), version 4.1.0, downloadable at [https ...

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

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 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 certain ...

Association for Computing Machinery2017

Cooperative Data Exchange with Weighted Cost based on d-Basis Construction

Michael Christoph Gastpar, Su Li, Abhin Shah

We consider the cooperative data exchange problem, in which nodes are fully connected with each other. Each node initially only has a subset of the K packets making up a file and wants to recover the whole file. Node i can make a broadcast transmission, wh ...

2017

GDSP: A graphical perspective on the distributed storage systems

Michael Christoph Gastpar, Saeid Sahraei

The classical distributed storage problem can be modeled by a k-uniform complete hyper-graph where vertices represent servers and hyper-edges represent users. Hence each hyper-edge should be able to recover the full file using only the memories of the vert ...

2017

Data Exchange Problem with Helpers

Graph Chatbot

Chat with Graph Search

Approximation Algorithms for Allocation and Network Design

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

On Polynomial Algorithms for Normalizing Formulas

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

New Results in Integer and Lattice Programming

Distance to the nearest land/coastline (including small subantarctic islands) for the five-minute average cruise track of the Antarctic Circumnavigation Expedition (ACE) during the austral summer of 2016/2017.

New Graph Algorithms via Polyhedral Techniques

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

Cooperative Data Exchange with Weighted Cost based on d-Basis Construction

GDSP: A graphical perspective on the distributed storage systems

On Polynomial Algorithms for Normalizing Formulas

Approximation Algorithms for Allocation and Network Design

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

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

New Results in Integer and Lattice Programming

New Graph Algorithms via Polyhedral Techniques

Distance to the nearest land/coastline (including small subantarctic islands) for the five-minute average cruise track of the Antarctic Circumnavigation Expedition (ACE) during the austral summer of 2016/2017.

Combinatorial Algorithm for Restricted Max-Min Fair Allocation

GDSP: A graphical perspective on the distributed storage systems

Cooperative Data Exchange with Weighted Cost based on d-Basis Construction