| 2023 | AAAI | An Improved Algorithm for Online Min-Sum Set Cover. | Marcin Bienkowski, Marcin Mucha |
| 2022 | AusDM | Improving Ads-Profitability Using Traffic-Fingerprints. | Adam Gabriel Dobrakowski, Andrzej Pacuk, Piotr Sankowski, Marcin Mucha, Pawel Brach |
| 2022 | IPCO | Matroid-Based TSP Rounding for Half-Integral Solutions. | Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar |
| 2019 | ESA | Equal-Subset-Sum Faster Than the Meet-in-the-Middle. | Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Wegrzycki |
| 2019 | SODA | A Subquadratic Approximation Scheme for Partition. | Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk |
| 2018 | ESA | Online Facility Location with Deletions. | Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski |
| 2017 | CPM | Shortest Superstring. | Marcin Mucha |
| 2017 | ICALP | Dynamic Beats Fixed: On Phase-Based Algorithms for File Migration. | Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha |
| 2017 | ICALP | On Problems Equivalent to (min, +)-Convolution. | Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk |
| 2016 | SODA | Online Pricing with Impatient Bidders. | Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang |
| 2014 | LATIN | New Bounds for Online Packing LPs. | Matthias Englert, Nicolaos Matsakis, Marcin Mucha |
| 2013 | ICALP | No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem. | Marcin Mucha, Maxim Sviridenko |
| 2013 | SODA | Lyndon Words and Short Superstrings. | Marcin Mucha |
| 2012 | STACS | 13/9-approximation for Graphic TSP. | Marcin Mucha |
| 2012 | WG | A 9k Kernel for Nonseparating Independent Set in Planar Graphs. | Lukasz Kowalik, Marcin Mucha |
| 2010 | ESA | Fast Approximation in Subspaces by Doubling Metric Decomposition. | Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski |
| 2009 | WADS | Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality. | Lukasz Kowalik, Marcin Mucha |
| 2007 | WADS | 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality. | Lukasz Kowalik, Marcin Mucha |
| 2004 | ESA | Maximum Matchings in Planar Graphs via Gaussian Elimination. | Marcin Mucha, Piotr Sankowski |
| 2004 | FOCS | Maximum Matchings via Gaussian Elimination. | Marcin Mucha, Piotr Sankowski |