Publications related to Network Formulations of Mixed-Integer Programs

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

Removing Algorithmic Discrimination (With Minimal Individual Error)

Rachid Guerraoui, El Mahdi El Mhamdi, Alexandre David Olivier Maurer, Le Nguyen Hoang

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

2022

Removing algorithmic discrimination (with minimal individual error)

Rachid Guerraoui, El Mahdi El Mhamdi, Alexandre David Olivier Maurer, Le Nguyen Hoang

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

ELSEVIER2022

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

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

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

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Verified Functional Programming

Nicolas Charles Yves Voirol

In this thesis, we present Stainless, a verification system for an expressive subset of the Scala language. Our system is based on a dependently-typed language and an algorithmic type checking procedure which ensures total correctness. We rely on SMT solve ...

EPFL2019

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2018

2018 FIFA World Cup: The group stage imbalance. Can we do better?

Gilles Baechler, Frederike Dümbgen, Miranda Krekovic, Golnooshsadat Elhami

Synopsis: Create a fair ranking system for the 2018 FIFA World Cup LCAV20171130 Level: BS, MS Description: Imagine that you are given the scores of all the 32 teams participating in the 2 ...

2018

Network Formulations of Mixed-Integer Programs

Graph Chatbot

Chat with Graph Search

Results on Sparse Integer Programming and Geometric Independent Sets

Removing Algorithmic Discrimination (With Minimal Individual Error)

Removing algorithmic discrimination (with minimal individual error)

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

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

New Results in Integer and Lattice Programming

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Verified Functional Programming

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

2018 FIFA World Cup: The group stage imbalance. Can we do better?

Results on Sparse Integer Programming and Geometric Independent Sets

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

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

New Results in Integer and Lattice Programming

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Removing Algorithmic Discrimination (With Minimal Individual Error)

Removing algorithmic discrimination (with minimal individual error)

Verified Functional Programming

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

2018 FIFA World Cup: The group stage imbalance. Can we do better?