Selected publications

Brief descriptions of selected papers; expand any entry to read more.

Matroid-based TSP rounding for half-integral solutions

Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar
Mathematical Programming 206 (2024), 541–576; IPCO 2022

Paper arXiv

Description

This paper studies rounding half-integral solutions of the traveling salesperson subtour relaxation into tours with a factor below 1.5. It combines matroid-intersection sampling and maximum-entropy ideas to improve the guarantee for these instances.

An Improved Algorithm for Online Min-Sum Set Cover

Marcin Bienkowski, Marcin Mucha
AAAI 2023, 6815–6822

Paper arXiv

Description

An online algorithm maintains an ordering while requests specify sets whose members should appear near the front. The paper compares the algorithm against an optimal ordering that can itself change over time, and obtains a randomized competitive ratio depending on request size rather than the total number of elements.

Improving Ads-Profitability Using Traffic-Fingerprints

Adam Gabriel Dobrakowski, Andrzej Pacuk, Piotr Sankowski, Marcin Mucha, Paweł Brach
AusDM 2022, 205–216

arXiv

Description

The paper represents a web page’s daily traffic as a normalized 24-dimensional fingerprint. Clustering pages by these patterns helps estimate advertising profitability even on pages with little traffic; the reported campaign experiments increased revenue by more than 50%.

Improved approximation for Fractionally Subadditive Network Design

Marcin Mucha, Marcin Smulewicz
Information Processing Letters 154 (2020), 105861

Paper

Description

The paper revisits fractionally subadditive network design and gives an improved approximation analysis with a simpler argument.

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth

Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki
IPEC 2020, 37:1–37:18

Paper

Description

A report on the 2020 PACE challenge, which focused on computing graph treedepth. It describes the competition and submissions from 20 teams across 12 countries.

Equal-Subset-Sum Faster Than the Meet-in-the-Middle

Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki
ESA 2019, 73:1–73:16

Paper arXiv

Description

For the problem of finding two disjoint, nonempty subsets of integers with equal sums, the paper improves the previous meet-in-the-middle running time with a randomized algorithm. It also gives a faster polynomial-space algorithm under a read-only random-bit assumption.

A Subquadratic Approximation Scheme for Partition Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk SODA 2019	arXiv
Description A randomized approximation scheme for Partition runs in subquadratic time in the combined input-size and accuracy parameters. The approach reduces Subset Sum to structured instances and also yields related results for other approximation problems.

Applying deep learning to right whale photo identification Robert Bogucki, Marek Cygan, Christin Brangwynne Khan, Maciej Klimek, Jan Kanty Milczek, Marcin Mucha Conservation Biology	Paper
Description A deep-learning workflow identifies individual North Atlantic right whales from photographs. Developed through a Kaggle challenge, the winning approach standardized images before matching them and achieved 87% identification accuracy.

Online Facility Location with Deletions Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski ESA 2018	arXiv
Description Studies online facility location when clients or facilities may disappear as well as arrive. It gives competitive algorithms for dynamic uncapacitated and capacitated variants, including the need to reconnect clients after a facility leaves.

On problems equivalent to (min, +)-convolution Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk ICALP 2017	arXiv
Description Develops reductions linking (min,+)-convolution to several other problems, including variants of knapsack and subadditive sequences. These connections clarify when faster algorithms for one problem would imply breakthroughs for another.

Dynamic beats fixed: on phase-based algorithms for file migration Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha ICALP 2017	arXiv
Description Gives a deterministic 4-competitive algorithm for online file migration by adjusting the lengths of its phases to observed requests. It also shows a limitation of fixed-length phase algorithms in a model with changing graphs.

Online Pricing with Impatient Bidders Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang SODA 2016	Manuscript
Description Studies online pricing for bidders who arrive at different times, have individual budgets, and buy at the earliest acceptable price. The seller sets prices over time to maximize revenue without knowing future bidders.

New Bounds for Online Packing LPs Matthias Englert, Nicolaos Matsakis, Marcin Mucha LATIN 2014	Manuscript
Description Studies online packing linear programs when the algorithm sees only approximate estimates of each constraint’s remaining capacity. It establishes new upper and lower bounds for this limited-information model.

No-Wait Flowshop Scheduling is as Hard as Asymmetric Traveling Salesman Problem Marcin Mucha, Maxim Sviridenko ICALP 2013 Mathematics of Operations Research 2016	Manuscript arXiv Paper
Description Connects no-wait flowshop scheduling to asymmetric traveling salesperson: an approximation for the scheduling problem would give nearly the same approximation for ATSP. The reduction transfers hardness results to no-wait scheduling.

Catch Them if You Can: Serving Impatient Users Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski ITCS 2013	Manuscript
Description Studies how to choose whom to serve when unserved customers may leave after each time step. The goal is to maximize expected collected value while balancing customer values against their risk of departure.

Lyndon Words and Short Superstrings Marcin Mucha SODA 2013	Manuscript arXiv
Description Improves the long-standing approximation bound for the shortest superstring problem, using a connection to maximum asymmetric TSP paths and structural properties of Lyndon words.

A 9k Kernel for Nonseparating Independent Set in Planar Graphs Łukasz Kowalik, Marcin Mucha WG 2012 Theoretical Computer Science 2014	arXiv Paper Paper
Description Gives a kernel with at most 9k vertices for planar maximum nonseparating independent set. It also derives consequences for connected vertex cover and a 5k-vertex kernel for planar maximum leaf.

13/9-approximation for Graphic TSP Marcin Mucha STACS 2012 Theory of Computing Systems (STACS 2012 issue)	arXiv Paper Paper
Description Improves the analysis of an algorithm for the graphic traveling salesperson problem to a 13/9 approximation. It also obtains a guarantee for a related path problem in graphic metrics.

Approximation Algorithms for Union and Intersection Covering Problems Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski FSTTCS 2011	arXiv Paper
Description Introduces multi-layer covering problems in which requests are shared across instances. A request can be satisfied in at least one layer (union) or in every layer (intersection), leading to new approximation questions.

Fast Dynamic Transitive Closure with Lookahead Marcin Mucha, Piotr Sankowski Algorithmica 56(2) 2010	Paper
Description Studies dynamic reachability with advance knowledge of upcoming operations. Randomized algorithms use this lookahead to speed up updates and queries, with further results for planar graphs and restricted updates.

Fast Approximation in Subspaces by Doubling Metric Decomposition Marek Cygan, Łukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski ESA 2010	arXiv Paper
Description Develops compact data structures for repeated approximation queries over doubling metrics. After preprocessing a graph, problems such as facility location, Steiner forest, and TSP can be answered quickly for selected subsets.

Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality Łukasz Kowalik, Marcin Mucha WADS 2009	Manuscript Paper
Description Presents two approximation algorithms for asymmetric TSP under a strengthened triangle inequality. Their guarantees improve earlier bounds over different ranges of the triangle-inequality parameter.

A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem Katarzyna E. Paluch, Marcin Mucha, Aleksander Mądry APPROX-RANDOM 2009	arXiv Paper
Description Gives a deterministic combinatorial algorithm achieving a 7/9 approximation for the symmetric maximum traveling salesperson problem.

*Deterministic 7/8-Approximation for the Metric Maximum TSP* Łukasz Kowalik, Marcin Mucha APPROX-RANDOM 2008 Journal version in Theor. Comput. Sci. 410(47-49) 2009	Paper Paper
Description Gives a deterministic 7/8 approximation for metric maximum TSP, improving earlier deterministic guarantees and matching the leading randomized factor without its loss term.

35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality Łukasz Kowalik, Marcin Mucha WADS 2007 Journal version in Algorithmica 59(2) 2011	Paper Paper
Description Improves the approximation factor for asymmetric maximum TSP with triangle inequality to 35/44.

Maximum Matchings via Gaussian Elimination Marcin Mucha, Piotr Sankowski FOCS 2004 (Best Student Paper)	Paper
Description Uses randomized Gaussian-elimination methods to find maximum matchings in general and bipartite graphs in matrix-multiplication time. This turns an algebraic test for perfect matching into a constructive algorithm.

Maximum Matchings in Planar Graphs via Gaussian Elimination Marcin Mucha, Piotr Sankowski ESA 2004 (Best Student Paper) Journal Version in Algorithmica 45(1) 2006	Paper Paper
Description Uses randomized Gaussian elimination to find maximum matchings in planar graphs in O(n^(ω/2)) arithmetic time. The paper also gives an algorithm for sampling perfect matchings in planar graphs uniformly at random.