Showing 2017Show all
2 papers · 1 filter
math.CO2017
Few Sequence Pairs Suffice: Representing All Rectangle Placements
Jannik Silvanus, Jens Vygen
We consider representations of general non-overlapping placements of rectangles by spatial relations (west, south, east, north) of pairs of rectangles. We call a set of representat…
cs.DM2017
On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Jochen Könemann, Neil Olver, Kanstantsin Pashkovich +3
In the prize-collecting Steiner forest (PCSF) problem, we are given an undirected graph , edge costs , terminal pairs , and…