DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2018.6

Tree Decomposition Methods for the Periodic Event Scheduling Problem

Authors: Irving van Heuven van Staereling

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract

This paper proposes an algorithm that decomposes the Periodic Event Scheduling Problem (PESP) into trees that can efficiently be solved. By identifying at an early stage which partial solutions can lead to a feasible solution, the decomposed components can be integrated back while maintaining feasibility if possible. If not, the modifications required to regain feasibility can be found efficiently. These techniques integrate dynamic programming into standard search methods. The performance of these heuristics are very satisfying, as the problem using publicly available benchmarks can be solved within a reasonable amount of time, in an alternative way than the currently accepted leading-edge techniques. Furthermore, these heuristics do not necessarily rely on linearity of the objective function, which facilitates the research of timetabling under nonlinear circumstances.

Cite as

Irving van Heuven van Staereling. Tree Decomposition Methods for the Periodic Event Scheduling Problem. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanheuvenvanstaereling:OASIcs.ATMOS.2018.6,
  author =	{van Heuven van Staereling, Irving},
  title =	{{Tree Decomposition Methods for the Periodic Event Scheduling Problem}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{6:1--6:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.6},
  URN =		{urn:nbn:de:0030-drops-97112},
  doi =		{10.4230/OASIcs.ATMOS.2018.6},
  annote =	{Keywords: Dynamic Programming, Trees, Periodic Event Scheduling Problem}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2016.50

The Ground-Set-Cost Budgeted Maximum Coverage Problem

Authors: Irving van Heuven van Staereling, Bart de Keijzer, and Guido Schäfer

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract

We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph G = (V, E), where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set of hyperedges T subseteq E such that the total cost of the vertices covered by T is at most B and the total profit of all covered vertices is maximized. Besides being a natural generalization of the well-studied maximum coverage problem, our motivation for investigating this problem originates from its application in the context of bid optimization in sponsored search auctions, such as Google AdWords. It is easily seen that this problem is strictly harder than budgeted max coverage, which means that the problem is (1-1/e)-inapproximable. The difference of our problem to the budgeted maximum coverage problem is that the costs are associated with the covered vertices instead of the selected hyperedges. As it turns out, this difference refutes the applicability of standard greedy approaches which are used to obtain constant factor approximation algorithms for several other variants of the maximum coverage problem. Our main results are as follows: - We obtain a (1 - 1/sqrt(e))/2-approximation algorithm for graphs. - We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i.e., the hypergraph is Berge-acyclic). We also extend this result to incidence graphs with a fixed-size feedback hyperedge node set. - We give a (1-epsilon)/(2d^2)-approximation algorithm for every epsilon > 0, where d is the maximum degree of a vertex in the hypergraph.

Cite as

Irving van Heuven van Staereling, Bart de Keijzer, and Guido Schäfer. The Ground-Set-Cost Budgeted Maximum Coverage Problem. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vanheuvenvanstaereling_et_al:LIPIcs.MFCS.2016.50,
  author =	{van Heuven van Staereling, Irving and de Keijzer, Bart and Sch\"{a}fer, Guido},
  title =	{{The Ground-Set-Cost Budgeted Maximum Coverage Problem}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.50},
  URN =		{urn:nbn:de:0030-drops-65020},
  doi =		{10.4230/LIPIcs.MFCS.2016.50},
  annote =	{Keywords: maximum coverage problem, approximation algorithms, hypergraphs, submodular optimization, sponsored search}
}

Search Results

Documents authored by van Heuven van Staereling, Irving

Tree Decomposition Methods for the Periodic Event Scheduling Problem

Abstract

Cite as

The Ground-Set-Cost Budgeted Maximum Coverage Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message