betaFeedback

WorksComputer Science

Path-constrained Packing on Trees

Abstract

An instance of Budgeted Path-constrained Packing on Trees (BPPT) consists of a graph GG together with a spanning tree TT, a weight we∈Z≥0w_e \in \mathbb{Z}_{\ge 0} for each tree edge e∈E(T)e \in E(T) and a budget bf∈Z≥1b_f \in \mathbb{Z}_{\ge 1} for each non-tree edge f∈E(G)∖E(T)f \in E(G) \setminus E(T). The goal is to find a maximum weight packing of fundamental cuts respecting the budgets. Equivalently, an instance of BPPT is an integer program of the form max⁡{w⊺x:Ax≤b, x∈{0,1}n}\max \{w^\intercal x : Ax \le b,\ x \in \{0,1\}^n\} where A∈{0,1}m×nA \in \{0,1\}^{m \times n} is a transposed edge-path-tree matrix, w∈Z≥0nw \in \mathbb{Z}^n_{\ge 0} and b∈Z≥1mb \in \mathbb{Z}^m_{\ge 1}. We define the congestion CC of a BPPT instance as the maximum number of non-zeros in a column of AA. The unit congestion UCUC is defined similarly, except that rows with bi≥2b_i \ge 2 are ignored. We also consider the minimum budget β:=min⁡{bi:i=1,…,m}β:= \min \{b_i : i = 1, \ldots, m\}. In this paper, we begin the study of BPPT through the lens of the three parameters CC, UCUC and ββ, and relative to the standard LP relaxation max⁡{w⊺x:Ax≤b, x∈[0,1]n}\max \{w^\intercal x : Ax \le b,\ x \in [0,1]^n\}. BPPT generalizes the independent set problem in graphs of maximum degree at most CC and is a special case of the bb-matching problem in hypergraphs of rank at most CC. We obtain approximation algorithms for BPPT with factors 2+UC/22+UC/2, 1+C/21+C/2 and β/(β−1)β/(β-1) for β≥2β\geq 2. These bounds are relative to the standard LP relaxation and, as we show, integrality gap tight with respect to parameters UCUC and ββ, and almost integrality gap tight relative to CC. We complement these results with a ⌈(C+1)/3⌉\lceil (C+1)/3 \rceil-approximation for fixed CC which is not relative to the standard LP relaxation and has XP\textsf{XP} running time parameterized by CC.

Paper details

vlnc:W_ukehxdgu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…