Marcin Mucha

Marcin Mucha

Auto-generated profile, based on publicly available information

Marcin Mucha

University of Warsaw

Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 December 2004
Verified
Conference Paper
Closed access
MMM. Mucha
M. Mucha
PSP. Sankowski
P. Sankowski

8 January 2019 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
MCMarek Cygan
Marek Cygan
MMMarcin Mucha
Marcin Mucha
KWKarol Węgrzycki
Karol Węgrzycki
MWMichał Włodarczyk
Michał Włodarczyk
In recent years, significant progress has been made in explaining the apparent hardness of improving upon the naive solutions for many fundamental polynomially solvable problems. This progress has come in the form of conditional lower bounds—reductions from a problem assumed to be hard. The hard problems include 3SUM, All-Pairs Shortest Path, SAT, Orthogonal Vectors, and others. In the (min ,+)-convolution problem, the goal is to compute a sequence ( c [ i ]) n-1 i=0 , where c [ k ] = min i=0,…; , k { a [ i ] + b [ k - i ]}, given sequences ( a [ i ]) n-1 i=0 and ( b [ i ]) n-1 i=0 . This can easily be done in O( n 2 ) time, but no O ( n 2-ε ) algorithm is known for ε > 0. In this article, we undertake a systematic study of the (min ,+)-convolution problem as a hardness assumption. First, we establish the equivalence of this problem to a group of other problems, including variants of the classic knapsack problem and problems related to subadditive sequences. The (min ,+)-convolution problem has been used as a building block in algorithms for many problems, notably problems in stringology. It has also appeared as an ad hoc hardness assumption. Second, we investigate some of these connections and provide new reductions and other results. We also explain why replacing this assumption with the Strong Exponential Time Hypothesis might not be possible for some problems.

7 December 2012 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
MMMarcin Mucha
Marcin Mucha
The Travelling Salesman Problem is one of the fundamental and intensively studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides’s algorithm with an approximation factor of \(\frac{3}{2}\), even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only \(\frac{4}{3}\). Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al. (FOCS, 550–559, 2011 ), and then by Mömke and Svensson (FOCS, 560–569, 2011 ). In this paper, we provide an improved analysis of the approach presented in Mömke and Svensson (FOCS, 560–569, 2011 ) yielding a bound of \(\frac{13}{9}\) on the approximation factor, as well as a bound of \(\frac{19}{12}+\varepsilon\) for any ε>0 for a more general Travelling Salesman Path Problem in graphic metrics.

1 May 2006 in Algorithmica
Verified
Journal Article
Closed access
PDF file
MMMarcin Mucha
Marcin Mucha
PSPiotr Sankowski
Piotr Sankowski

Verified
Conference Paper
Open access
PDF file
MMMarcin Mucha
Marcin Mucha
The Travelling Salesman Problem is one of the most fundamental and most studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with approximation factor of 3/2, even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only 4/3. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al. (2011), and then by Momke and Svensson (2011). In this paper, we provide an improved analysis of the approach used by the latter, yielding a bound of 13/9 on the approximation factor, as well as a bound of 19/12+epsilon for any epsilon>0 for a more general Travelling Salesman Path Problem in graphic metrics.

25 January 2008 in Algorithmica
Verified
Journal Article
Closed access
PDF file
PSPiotr Sankowski
Piotr Sankowski
MMMarcin Mucha
Marcin Mucha