Source author record

Mateusz Lewandowski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Dense Steiner problems: Approximation algorithms and inapproximability

The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set $T$ of terminals in a graph $G$ by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the $δ$ -dense version of {\sc Steiner Tree}, where each terminal has at least $δ|V(G)\setminus T|$ neighbours outside $T$ , for a fixed $δ> 0$ . They gave a PTAS for this problem. We study a generalization of pairwise $δ$ -dense {\sc Steiner Forest}, which asks for a minimum-size forest in $G$ in which the nodes in each terminal set $T_1,\dots,T_k$ are connected, and every terminal in $T_i$ has at least $δ|T_j|$ neighbours in $T_j$ , and at least $δ|S|$ nodes in $S = V(G)\setminus (T_1\cup\dots\cup T_k)$ , for each $i, j$ in $\{1,\dots, k\}$ with $i\neq j$ . Our first result is a polynomial-time approximation scheme for all $δ> 1/2$ . Then, we show a $(\frac{13}{12}+\varepsilon)$ -approximation algorithm for $δ= 1/2$ and any $\varepsilon > 0$ . We also consider the $δ$ -dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is $\mathsf{APX}$ -hard.

preprint2016arXiv

Approximation algorithms for node-weighted prize-collecting Steiner tree problems on planar graphs

We study the prize-collecting version of the Node-weighted Steiner Tree problem (NWPCST) restricted to planar graphs. We give a new primal-dual Lagrangian-multiplier-preserving (LMP) 3-approximation algorithm for planar NWPCST. We then show a ( $2.88 + ε$ )-approximation which establishes a new best approximation guarantee for planar NWPCST. This is done by combining our LMP algorithm with a threshold rounding technique and utilizing the 2.4-approximation of Berman and Yaroslavtsev for the version without penalties. We also give a primal-dual 4-approximation algorithm for the more general forest version using techniques introduced by Hajiaghay and Jain.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.