<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>691</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-05-07</completedDate>
    <publishedDate>2002-05-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Budgeted Maximal Graph Coverage</title>
    <abstract language="eng">An instance of the \emph{maximum coverage} problem is given by a set of weighted ground elements and a cost weighted family of subsets of the ground element set. The goal is to select a subfamily of total cost of at most that of a given budget maximizing the weight of the covered elements. We formulate the problem on graphs: In this situation the set of ground elements is specified by the nodes of a graph, while the family of covering sets is restricted to connected subgraphs. We show that on general graphs the problem is polynomial time solvable if restricted to sets of size at most~$2$, but becomes NP-hard if sets of size~$3$ are permitted. On trees, we prove polynomial time solvability if each node appears in a fixed number of sets. In contrast, if vertices are allowed to appear an unbounded number of times, the problem is NP-hard even on stars. We finally give polynomial time algorithms for special cases where the subgraphs form paths and the host graph is a line, a cycle or a star.</abstract>
    <identifier type="serial">02-24</identifier>
    <identifier type="opus3-id">692</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6918</identifier>
    <enrichment key="SourceTitle">Appeared in: Graph-Theoretic Concepts in Computer Science. 28th Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002; revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 321-332</enrichment>
    <author>Sven Krumke</author>
    <author>Madhav Marathe</author>
    <author>Diana Poensgen</author>
    <author>Sekharipuram S. Ravi</author>
    <author>Hans-Christoph Wirth</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-24</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>budgeted maximum coverage</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>approximation algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>dynamic programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q17">Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) [See also 68Q15]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/691/ZR-02-24.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/691/ZR-02-24.pdf</file>
  </doc>
  <doc>
    <id>578</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-03-24</completedDate>
    <publishedDate>2000-03-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Budget Constrained Minimum Cost Connected Medians</title>
    <abstract language="eng">Several practical instances of network design problems require the network to satisfy multiple constraints. In this paper, we address the \emph{Budget Constrained Connected Median Problem}: We are given an undirected graph $G = (V,E)$ with two different edge-weight functions $c$ (modeling the construction or communication cost) and $d$ (modeling the service distance), and a bound~$B$ on the total service distance. The goal is to find a subtree~$T$ of $G$ with minimum $c$-cost $c(T)$ subject to the constraint that the sum of the service distances of all the remaining nodes $v \in V\setminus T$ to their closest neighbor in~$T$ does not exceed the specified budget~$B$. This problem has applications in optical network design and the efficient maintenance of distributed databases. We formulate this problem as bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem that demonstrate that our performance ratios are close to best possible</abstract>
    <identifier type="serial">00-10</identifier>
    <identifier type="opus3-id">579</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-5783</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science, Konstanz, Germany, Vol 1928 of Lecture Notes in Computer Science, Springer Jun 2000, 267-278</enrichment>
    <author>Goran Konjevod</author>
    <author>Sven Krumke</author>
    <author>Madhav Marathe</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-10</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NP-hardness</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Approximation Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q15">Complexity classes (hierarchies, relations among complexity classes, etc.) [See also 03D15, 68Q17, 68Q19]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/578/ZR-00-10.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/578/ZR-00-10.pdf</file>
  </doc>
</export-example>
