1 citations · 1 across the 7 of their papers we have counts for
6 papers · 1 filter
A Technique for Obtaining True Approximations for -Center with Covering Constraints
Georg Anegg, Haris Angelidakis, Adam Kurpisz +1
There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the -Center problem in this s…
New Dependencies of Hierarchies in Polynomial Optimization
Adam Kurpisz, Timo de Wolff
We compare four key hierarchies for solving Constrained Polynomial Optimization Problems (CPOP): Sum of Squares (SOS), Sum of Diagonally Dominant Polynomials (SDSOS), Sum of Nonneg…
Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials
Mareike Dressler, Adam Kurpisz, Timo de Wolff
Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove com…
A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
The Min-sum single machine scheduling problem (denoted 1||sum f_j) generalizes a large number of sequencing problems. The first constant approximation guarantees have been obtained…
Sum-of-squares hierarchy lower bounds for symmetric formulations
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical…
Approximability of the robust representatives selection problem
Adam Kasperski, Adam Kurpisz, Pawel Zielinski
In this paper new complexity and approximation results on the robust versions of the representatives selection problem, under the scenario uncertainty representation, are provided,…