Marcin Mucha

AAAI Conference 2023 Conference Paper

An Improved Algorithm for Online Min-Sum Set Cover

• Marcin Bienkowski
• Marcin Mucha

We study a fundamental model of online preference aggregation, where an algorithm maintains an ordered list of n elements. An input is a stream of preferred sets R_1, R_2,..., R_t,... Upon seeing R_t and without knowledge of any future sets, an algorithm has to rerank elements (change the list ordering), so that at least one element of R_t is found near the list front. The incurred cost is a sum of the list update costs (the number of swaps of neighboring list elements) and access cost (the position of the first element of R_t on the list). This scenario occurs naturally in applications such as ordering items in an online shop using aggregated preferences of shop customers. The theoretical underpinning of this problem is known as Min-Sum Set Cover. Unlike previous work that mostly studied the performance of an online algorithm ALG in comparison to the static optimal solution (a single optimal list ordering), in this paper, we study an arguably harder variant where the benchmark is the provably stronger optimal dynamic solution OPT (that may also modify the list ordering). In terms of an online shop, this means that the aggregated preferences of its user base evolve with time. We construct a computationally efficient randomized algorithm whose competitive ratio (ALG-to-OPT cost ratio) is O(r^2) and prove the existence of a deterministic O(r^4)-competitive algorithm. Here, r is the maximum cardinality of sets R_t. This is the first algorithm whose ratio does not depend on n: the previously best algorithm for this problem was O(r^(3/2) * n^(1/2))-competitive and Ω(r) is a lower bound on the performance of any deterministic online algorithm.

SODA Conference 2019 Conference Paper

A Subquadratic Approximation Scheme for Partition

• Marcin Mucha
• Karol Wegrzycki
• Michal Wlodarczyk 0001

The subject of this paper is the time complexity of approximating K napsack, S ubset S um, P artition, and some other related problems. The main result is an Õ ( n + 1/ ε 5/3 ) time randomized FPTAS for P artition, which is derived from a certain relaxed form of a randomized FPTAS for S ubset S um. To the best of our knowledge, this is the first NP-hard problem that has been shown to admit a subquadratic time approximation scheme, i. e. , one with time complexity of O (( n + 1/ ε 2–δ ) for some δ > 0. To put these developments in context, note that a quadratic FPTAS for P artition has been known for 40 years. Our main contribution lies in designing a mechanism that reduces an instance of S ubset S um to several simpler instances, each with some special structure, and keeps track of interactions between them. This allows us to combine techniques from approximation algorithms, pseudo-polynomial algorithms, and additive combinatorics. We also prove several related results. Notably, we improve approximation schemes for 3SUM, (min, +)-convolution, and T ree S parsity. Finally, we argue why breaking the quadratic barrier for approximate K napsack is unlikely by giving an Ω(( n + 1/ ε ) 2– o (1) ) conditional lower bound.

SODA Conference 2016 Conference Paper

Online Pricing with Impatient Bidders

• Marek Cygan
• Marcin Mucha
• Piotr Sankowski
• Qiang Zhang

TCS Journal 2014 Journal Article

A 9 k kernel for nonseparating independent set in planar graphs

• Łukasz Kowalik
• Marcin Mucha

We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. We focus on the Planar Maximum Nonseparating Independent Set problem, where given a planar graph and an integer k one has to find an independent set of size k whose removal leaves the graph connected. Our main result is a kernel of size at most 9k vertices for this problem. A direct consequence of this result is that Planar Connected Vertex Cover has no kernel with at most ( 9 / 8 − ϵ ) k vertices, for any ϵ > 0, assuming P ≠ NP. As a by-product we show extremal graph theory results which might be of independent interest. We prove that graphs that contain no separator consisting of only degree two vertices contain (a) a spanning tree with at least n / 4 leaves and (b) a nonseparating independent set of size at least n / 9 (also, equivalently, a connected vertex cover of size at most 8 9 n ). The result (a) is a generalization of a theorem of Kleitman and West [12] who showed the same bound for graphs of minimum degree three. Finally, we show that every n-vertex outerplanar graph contains an independent set I and a collection of vertex-disjoint cycles C such that 9 | I | ⩾ 4 n − 3 | C |.

SODA Conference 2013 Conference Paper

Lyndon Words and Short Superstrings

• Marcin Mucha

In the shortest superstring problem, we are given a set of strings { s 1, …, s k } and want to find a string that contains all s i as substrings and has minimum length. This is a classical problem in approximation and the best known approximation factor is, given by Sweedyk [19] in 1999. Since then no improvement has been made, howerever two other approaches yielding a -approximation algorithms have been proposed by Kaplan et al. [10] and recently by Paluch et al. [16] — both based on a reduction to maximum asymmetric TSP path (Max-ATSP-Path) and structural results of Breslauer et al. [5]. In this paper we give an algorithm that achieves an approximation ratio of, breaking through the longstanding bound of. We use the standard reduction of S hortest -S uperstring to M ax -ATSP-P ath. The new, somewhat surprising, algorithmic idea is to take the better of the two solutions obtained by using: (a) the currently best -approximation algorithm for Max-ATSP-P ath and (b) a naïve cycle-cover based -approximation algorithm. To prove that this indeed results in an improvement, we further develop a theory of string overlaps, extending the results of Breslauer et al. [5]. This theory is based on the novel use of Lyndon words, as a substitute for generic unbordered rotations and critical factorizations, as used by Breslauer et al.

TCS Journal 2009 Journal Article

Deterministic 7 / 8 -approximation for the metric maximum TSP

• Łukasz Kowalik
• Marcin Mucha

We present the first 7 / 8 -approximation algorithm for the maximum Traveling Salesman Problem (MAX-TSP) with triangle inequality. Our algorithm is deterministic. This improves over both the randomized algorithm of Hassin and Rubinstein [R. Hassin, S. Rubinstein, A 7/8-approximation algorithm for metric Max TSP, Inf. Process. Lett. 81 (5) (2002) 247–251] with an expected approximation ratio of 7 / 8 − O ( n − 1 / 2 ) and the deterministic ( 7 / 8 − O ( n − 1 / 3 ) ) -approximation algorithm of Chen and Nagoya [Z. -Z. Chen, T. Nagoya, Improved approximation algorithms for metric max TSP, in: Proc. ESA’05, 2005, pp. 179–190]. In the new algorithm, we extend the approach of processing local configurations using the so-called loose-ends, which we introduced in [Ł. Kowalik, M. Mucha, 35/44-approximation for asymmetric maximum TSP with triangle inequality, in: Proc. 10th Workshop on Algorithms and Data Structures, WADS’07, 2007, pp. 590–601].

FOCS Conference 2004 Conference Paper

Maximum Matchings via Gaussian Elimination

• Marcin Mucha
• Piotr Sankowski

We present randomized algorithms for finding maximum matchings in general and bipartite graphs. Both algorithms have running time O(n/sup w/), where w is the exponent of the best known matrix multiplication algorithm. Since w < 2. 38, these algorithms break through the O(n/sup 2. 5/) barrier for the matching problem. They both have a very simple implementation in time O(n/sup 3/) and the only non-trivial element of the O(n/sup w/) bipartite matching algorithm is the fast matrix multiplication algorithm. Our results resolve a long-standing open question of whether Lovasz's randomized technique of testing graphs for perfect matching in time O(n/sup w/) can be extended to an algorithm that actually constructs a perfect matching.