<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>600</id>
    <completedYear>2024</completedYear>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>21</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>2025-05-12</completedDate>
    <publishedDate>2024-09-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem</title>
    <abstract language="eng">We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial (α,μ)-approximation is possible, i.e., a solution that with budget B+α for all B∈R≥0 is a multiplicative μ-approximation compared to the optimum solution with budget B. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a (χ,1)-approximation, where χ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is (γ,2)-competitive where γ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a (γ,3)-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a (3χ,8)-approximation and, more generally, a ((4ℓ−1)χ,(2^(ℓ+2))/(2^ℓ−1))-approximation for every fixed ℓ∈N.</abstract>
    <enrichment key="opus.source">publish</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <author>Yann Disser</author>
    <author>Svenja M. Griesbach</author>
    <author>Max Klimm</author>
    <author>Annette Lutz</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>incremental maximization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitive analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>prize-collecting Steiner-tree</value>
    </subject>
    <collection role="institutes" number="">Technische Universität Darmstadt</collection>
    <collection role="institutes" number="">Technische Universität Berlin</collection>
    <collection role="subprojects" number="">A07</collection>
    <collection role="subprojects" number="">A09</collection>
    <file>https://opus4.kobv.de/opus4-trr154/files/600/Incremental_Price-Collecting_Steiner-Tree.pdf</file>
  </doc>
</export-example>
