4 citations · 4 across the 4 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2020
Optimal polynomial-time compression for Boolean Max CSP
Bart M. P. Jansen, Michał Włodarczyk
In the Boolean maximum constraint satisfaction problem - Max CSP - one is given a collection of weighted applications of constraints from a finite constraint language , ove…
cs.CC2019
Parameterized inapproximability for Steiner Orientation by Gap Amplification
Michał Włodarczyk
In the -Steiner Orientation problem, we are given a mixed graph, that is, with both directed and undirected edges, and a set of terminal pairs. The goal is to find an orient…
cs.CC2017★ 4 cited
When the Optimum is also Blind: a New Perspective on Universal Optimization
Marek Adamczyk, Fabrizio Grandoni, Stefano Leonardi +1
Consider the following variant of the set cover problem. We are given a universe and a collection of subsets where …