Coloration gloutonne

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

Frequency-Domain Non-intrusive Greedy Model Order Reduction Based on Minimal Rational Approximation

Buddhima Ruwanmini Gamlath Gamlath Ralalage

We present a technique for Model Order Reduction (MOR) of frequency-domain problems relying on rational interpolation of vector-valued functions. The selection of the sample points is carried out adaptively according to a greedy procedure. We describe seve ...

SPRINGER INTERNATIONAL PUBLISHING AG2021

Cluster-and-Conquer: When Randomness Meets Graph Locality

Anne-Marie Kermarrec

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...

IEEE COMPUTER SOC2021

How to Match in Modern Computational Settings

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

EPFL2021

MATHICSE Technical Report : Frequency-domain non-intrusive greedy Model Order Reduction based on minimal rational approximation

Slobodan Mitrovic, Mikhail Kapralov, Ashkan Norouzi Fard, Jakab Tardos

MATHICSE2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

IEEE COMPUTER SOC2019

Distributed Coloring of Graphs with an Optimal Number of Colors

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

An ordered graph G(

COMENIUS UNIV2019

Ordered graphs and large bi-cliques in intersection graphs of curves

Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

Online Matching with General Arrivals

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

IEEE COMPUTER SOC2019

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Reduced Numerical Approximation of Reduced Fluid-Structure Interaction Problems With Applications in Hemodynamics

Simone Deparis, Claudia Maria Colciago

This paper deals with fast simulations of the hemodynamics in large arteries by considering a reduced model of the associated fluid-structure interaction problem, which in turn allows an additional reduction in terms of the numerical discretisation. The re ...

2018

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Slobodan Mitrovic, Ilija Bogunovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

Maximizing k-Submodular Functions and Beyond

Daniel Kressner, Jonas Ballani

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k >= 2 and 1

Assoc Computing Machinery2016

Space lower bounds for low-stretch greedy embeddings

Christos Kalaitzis

Greedy (geometric) routing is an important paradigm for routing in communication networks. It uses an embedding of the nodes of a network into points of a space (e.g., R-d) equipped with a distance function (e.g., the Euclidean distance l(2)) and uses as a ...

Elsevier Science Bv2016

Reduced Basis Methods: From Low-Rank Matrices To Low-Rank Tensors

We propose a novel combination of the reduced basis method with low-rank tensor techniques for the efficient solution of parameter-dependent linear systems in the case of several parameters. This combination, called rbTensor, consists of three ingredients. ...

Siam Publications2016

Sparse Group Covers and Greedy Tree Approximations

Volkan Cevher, Luca Baldassarre

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. ...

2015

Publications associées (25)

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Maryam Kamgarpour

IEEE2023

Approximation Algorithms for Allocation and Network Design

EPFL2023

Frequency-Domain Non-intrusive Greedy Model Order Reduction Based on Minimal Rational Approximation

Buddhima Ruwanmini Gamlath Gamlath Ralalage

SPRINGER INTERNATIONAL PUBLISHING AG2021

Cluster-and-Conquer: When Randomness Meets Graph Locality

Anne-Marie Kermarrec

IEEE COMPUTER SOC2021

How to Match in Modern Computational Settings

EPFL2021

MATHICSE Technical Report : Frequency-domain non-intrusive greedy Model Order Reduction based on minimal rational approximation

Slobodan Mitrovic, Mikhail Kapralov, Ashkan Norouzi Fard, Jakab Tardos

MATHICSE2020

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

ASSOC COMPUTING MACHINERY2020

Tight Bounds for Online Edge Coloring

David Wajc

IEEE COMPUTER SOC2019

Distributed Coloring of Graphs with an Optimal Number of Colors

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

An ordered graph G(

COMENIUS UNIV2019

Ordered graphs and large bi-cliques in intersection graphs of curves

Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

Online Matching with General Arrivals

IEEE COMPUTER SOC2019

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov

IEEE COMPUTER SOC2018

Reduced Numerical Approximation of Reduced Fluid-Structure Interaction Problems With Applications in Hemodynamics

Simone Deparis, Claudia Maria Colciago

2018

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Slobodan Mitrovic, Ilija Bogunovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

INFORMS2017

Maximizing k-Submodular Functions and Beyond