Marcin Mucha

According to our database, Marcin Mucha authored at least 31 papers between 2004 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Matroid-based TSP rounding for half-integral solutions.

Anupam Gupta, Euiwoong Lee, Jason Li, Marcin Mucha, Heather Newman, Sherry Sarkar

Math. Program., July, 2024

2023

An Improved Algorithm for Online Min-Sum Set Cover.

Marcin Bienkowski, Marcin Mucha

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

An Improved Algorithm For Online Reranking.

Marcin Bienkowski, Marcin Mucha

CoRR, 2022

Improving Ads-Profitability Using Traffic-Fingerprints.

Adam Gabriel Dobrakowski, Andrzej Pacuk, Piotr Sankowski, Marcin Mucha, Pawel Brach

Proceedings of the Data Mining - 20th Australasian Conference, AusDM 2022, Western Sydney, 2022

2020

Improved approximation for Fractionally Subadditive Network Design.

Marcin Mucha, Marcin Smulewicz

Inf. Process. Lett., 2020

The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.

Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, Piotr Wygocki

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

2019

On Problems Equivalent to (min, +)-Convolution.

Marek Cygan, Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk

ACM Trans. Algorithms, 2019

Dynamic Beats Fixed: On Phase-based Algorithms for File Migration.

Marcin Bienkowski, Jaroslaw Byrka, Marcin Mucha

ACM Trans. Algorithms, 2019

A Subquadratic Approximation Scheme for Partition.

Marcin Mucha, Karol Wegrzycki, Michal Wlodarczyk

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Wegrzycki

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Online Facility Location with Deletions.

Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Shortest Superstring.

Marcin Mucha

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016

Maximum Matching.

Marcin Mucha

Encyclopedia of Algorithms, 2016

No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem.

Marcin Mucha, Maxim Sviridenko

Math. Oper. Res., 2016

Online Pricing with Impatient Bidders.

Marek Cygan, Marcin Mucha, Piotr Sankowski, Qiang Zhang

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2014

A 9k kernel for nonseparating independent set in planar graphs.

Lukasz Kowalik, Marcin Mucha

Theor. Comput. Sci., 2014

13/9 -Approximation for Graphic TSP.

Marcin Mucha

Theory Comput. Syst., 2014

New Bounds for Online Packing LPs.

Matthias Englert, Nicolaos Matsakis, Marcin Mucha

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

2013

Lyndon Words and Short Superstrings.

Marcin Mucha

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Catch them if you can: how to serve impatient users.

Marek Cygan, Matthias Englert, Anupam Gupta, Marcin Mucha, Piotr Sankowski

Proceedings of the Innovations in Theoretical Computer Science, 2013

2011

Improved Analysis for Graphic TSP Approximation via Matchings

Marcin Mucha

CoRR, 2011

35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality.

Lukasz Kowalik, Marcin Mucha

Algorithmica, 2011

Approximation Algorithms for Union and Intersection Covering Problems.

Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

2010

Fast Dynamic Transitive Closure with Lookahead.

Piotr Sankowski, Marcin Mucha

Algorithmica, 2010

Fast Approximation in Subspaces by Doubling Metric Decomposition.

Marek Cygan, Lukasz Kowalik, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski

Proceedings of the Algorithms, 2010

2009

Deterministic 7/8-approximation for the metric maximum TSP.

Lukasz Kowalik, Marcin Mucha

Theor. Comput. Sci., 2009

Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality.

Lukasz Kowalik, Marcin Mucha

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem.

Katarzyna E. Paluch, Marcin Mucha, Aleksander Madry

Proceedings of the Approximation, 2009

2008

Maximum Matching.

Marcin Mucha

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

2006

Maximum Matchings in Planar Graphs via Gaussian Elimination.

Marcin Mucha, Piotr Sankowski

Algorithmica, 2006

2004

Maximum Matchings via Gaussian Elimination.

Marcin Mucha, Piotr Sankowski

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004