Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Maximum flow problem

Related publications (31)

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

Weighted Matchings via Unweighted Augmentations

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Sagar Sudhir Kale

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

ASSOC COMPUTING MACHINERY2019

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 in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

Generalized Turan problems for disjoint copies of graphs

Abhishek Methuku

Given two graphs H and F, the maximum possible number of copies of H in an F-free graph on n vertices is denoted by ex(n, H, F). We investigate the function ex(n, H, kF), where kF denotes k vertex disjoint copies of a fixed graph F. Our results include cas ...

Elsevier2019

Round Compression for Parallel Matching Algorithms

Slobodan Mitrovic, Aleksander Madry

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th ...

ASSOC COMPUTING MACHINERY2018

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Application of the Rosenbrock methods to the solution of unsteady 3D incompressible Navier-Stokes equations

Alfio Quarteroni, Michel Deville, Simone Deparis, Luca Pegolotti, Filippo Menghini

We consider the Rosenbrock methods, namely a family of methods for Differential Algebraic Equations, for the solution of the unsteady three-dimensional Navier-Stokes equations. These multistage schemes are attractive for non-linear problems because they ac ...

2018

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Bernard Moret, Mingfu Shao

A fundamental problem in comparative genomics is to compute the distance between two genomes in terms of its higher level organization (given by genes or syntenic blocks). For two genomes without duplicate genes, we can easily define (and almost always eff ...

Mary Ann Liebert, Inc2017

Automated Taxonomy Induction and its Applications

Amit Gupta

Machine-readable semantic knowledge in the form of taxonomies (i.e., a collection of is-a edges) has proved to be beneficial in an array of NLP tasks including inference, textual entailment, question answering and information extraction. Such widespread ut ...

EPFL2017