Showing cs.DSShow all
3 papers · 1 filter
cs.DS2020
Dense Steiner problems: Approximation algorithms and inapproximability
Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum +1
The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set of terminals in a graph by a tree of minimum size. Karpinski and…
cs.DS2019
PTAS for Steiner Tree on Map Graphs
Jarosław Byrka, Mateusz Lewandowski, Syed Mohammad Meesum +2
We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map grap…
cs.DS2019
Concave connection cost Facility Location and the Star Inventory Routing problem
Jarosław Byrka, Mateusz Lewandowski
We study a variant of the uncapacitated facility location problem (UFL), where connection costs of clients are defined by (client specific) concave nondecreasing functions of the c…