Publications related to Maximum flow problem

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.

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algori ...

EPFL2021

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Local approximation of the Maximum Cut in regular graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

ELSEVIER2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

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

Optimal spanwise-periodic control for recirculation length in a backward-facing step flow

François Gallaire, Edouard Boujo, Eunok Yim

Three-dimensional control is considered in the flow past a backward-facing step (BFS). The BFS flow at Reynolds number Re = 500 (defined with the step height and the maximum inlet velocity) is two-dimensional and linearly stable but increasingly receptive ...

AMER PHYSICAL SOC2020

Numerical Approximation Of Orthogonal Maps

Marco Picasso, Alexandre Caboussat, Dimitrios Gourzoulidis

Orthogonal maps are the solutions of the mathematical model of paper-folding, also called the origami problem. They consist of a system of first-order fully nonlinear equations involving the gradient of the solution. The Dirichlet problem for orthogonal ma ...

2019

Construction of Polar Codes With Sublinear Complexity

Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli

Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019

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

Maximum flow problem

Graph Chatbot

Chat with Graph Search

How to Match in Modern Computational Settings

Knapsack and Subset Sum with Small Items

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Local approximation of the Maximum Cut in regular graphs

Symbolic Algorithms for Token Swapping

New Results in Integer and Lattice Programming

Optimal spanwise-periodic control for recirculation length in a backward-facing step flow

Memory Efficient Max Flow for Multi-Label Submodular MRFs

Numerical Approximation Of Orthogonal Maps

Construction of Polar Codes With Sublinear Complexity

Local approximation of the Maximum Cut in regular graphs

How to Match in Modern Computational Settings

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

New Results in Integer and Lattice Programming

Numerical Approximation Of Orthogonal Maps

Optimal spanwise-periodic control for recirculation length in a backward-facing step flow

Memory Efficient Max Flow for Multi-Label Submodular MRFs

Symbolic Algorithms for Token Swapping

Construction of Polar Codes With Sublinear Complexity

Knapsack and Subset Sum with Small Items