Publications related to On the computational complexity of periodic scheduling

Results on Sparse Integer Programming and Geometric Independent Sets

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

Channel-Aware 5G RAN Slicing with Customizable Schedulers

Haitham Al Hassanieh

This paper focuses on 5G RAN slicing, where the 5G radio resources must be divided across slices (or enterprises) so as to achieve high spectrum efficiency, fairness and isolation across slices, and the ability for each slice to customize how the radio res ...

USENIX ASSOC2023

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

Minimum Cost Intervention Design for Causal Effect Identification

Negar Kiyavash, Sina Akbari, Seyed Jalal Etesami

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

PMLR2022

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Flow Time Scheduling and Prefix Beck-Fiala

Ola Nils Anders Svensson, Lars Rohwedder

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bound ...

ASSOC COMPUTING MACHINERY2022

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

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen, Ashkan Norouzi Fard

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model t ...

ASSOC COMPUTING MACHINERY2020

Fully dynamic bin packing revisited

Kim-Manuel Klein, Klaus Jansen

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. ...

SPRINGER HEIDELBERG2020

Graph fragmentation problem: analysis and synthesis

Manuel Francesco Aprile

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of indivi ...

WILEY2019

On the computational complexity of periodic scheduling

Graph Chatbot

Chat with Graph Search

Results on Sparse Integer Programming and Geometric Independent Sets

Channel-Aware 5G RAN Slicing with Customizable Schedulers

Discrete Optimal Transport with Independent Marginals is #P-Hard

Minimum Cost Intervention Design for Causal Effect Identification

The double exponential runtime is tight for 2-stage stochastic ILPs

Flow Time Scheduling and Prefix Beck-Fiala

New Results in Integer and Lattice Programming

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Fully dynamic bin packing revisited

Graph fragmentation problem: analysis and synthesis

Results on Sparse Integer Programming and Geometric Independent Sets

Channel-Aware 5G RAN Slicing with Customizable Schedulers

Discrete Optimal Transport with Independent Marginals is #P-Hard

New Results in Integer and Lattice Programming

Flow Time Scheduling and Prefix Beck-Fiala

The double exponential runtime is tight for 2-stage stochastic ILPs

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Graph fragmentation problem: analysis and synthesis

Fully dynamic bin packing revisited

Minimum Cost Intervention Design for Causal Effect Identification