6 citations · 6 across the 7 of their papers we have counts for
7 papers
A parameterized approximation scheme for the 2D-Knapsack problem with wide items
Michal Pilipczuk, Mathieu Mari, Timothe Picavet
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal…
On price-induced minmax matchings
Christoph Dürr, Mathieu Mari, Ulrike Schmidt-Kraepelin
We study a natural combinatorial pricing problem for sequentially arriving buyers with equal budgets. Each buyer is interested in exactly one pair of items and purchases this pair…
Online matching with delays and stochastic arrival times
Mathieu Mari, Michał Pawłowski, Runtian Ren +1
This paper presents a new research direction for the Min-cost Perfect Matching with Delays (MPMD) - a problem introduced by Emek et al. (STOC'16). In the original version of this p…
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
Waldo Gálvez, Arindam Khan, Mathieu Mari +3
We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overl…
Approximating maximum integral multiflows on bounded genus graphs
Chien-chung Huang, Mathieu Mari, Claire Mathieu +1
We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with t…
Ultimate greedy approximation of independent sets in subcubic graphs
Piotr Krysta, Mathieu Mari, Nan Zhi
We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization pro…
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
Chien-Chung Huang, Mathieu Mari, Claire Mathieu +2
We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges form a planar…