3 Search Results for "Spieksma, Frits C. R."

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.45
Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

Authors: Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Consider a problem where 4k given vectors need to be partitioned into k clusters of four vectors each. A cluster of four vectors is called a quad, and the cost of a quad is the sum of the component-wise maxima of the four vectors in the quad. The problem is to partition the given 4k vectors into k quads with minimum total cost. We analyze a straightforward matching-based algorithm and prove that this algorithm is a 3/2-approximation algorithm for this problem. We further analyze the performance of this algorithm on a hierarchy of special cases of the problem and prove that, in one particular case, the algorithm is a 5/4-approximation algorithm. Our analysis is tight in all cases except one.
Cite as

Annette M. C. Ficker, Thomas Erlebach, Matús Mihalák, and Frits C. R. Spieksma. Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 45:1-45:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ficker_et_al:LIPIcs.ISAAC.2018.45,
  author =	{Ficker, Annette M. C. and Erlebach, Thomas and Mihal\'{a}k, Mat\'{u}s and Spieksma, Frits C. R.},
  title =	{{Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.45},
  URN =		{urn:nbn:de:0030-drops-99933},
  doi =		{10.4230/LIPIcs.ISAAC.2018.45},
  annote =	{Keywords: approximation algorithm, matching, clustering problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.27
The Lockmaster's problem

Authors: Sofie Coene and Frits C. R. Spieksma

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.
Cite as

Sofie Coene and Frits C. R. Spieksma. The Lockmaster's problem. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 27-37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{coene_et_al:OASIcs.ATMOS.2011.27,
  author =	{Coene, Sofie and Spieksma, Frits C. R.},
  title =	{{The Lockmaster's problem}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{27--37},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.27},
  URN =		{urn:nbn:de:0030-drops-32647},
  doi =		{10.4230/OASIcs.ATMOS.2011.27},
  annote =	{Keywords: lock scheduling, batch scheduling, dynamic programming, complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.34
Heuristics for the Traveling Repairman Problem with Profits

Authors: Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, and Pieter Vansteenwegen

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
In the traveling repairman problem with profits, a repairman (also known as the server) visits a subset of nodes in order to collect time-dependent profits. The objective consists of maximizing the total collected revenue. We restrict our study to the case of a single server with nodes located in the Euclidean plane. We investigate properties of this problem, and we derive a mathematical model assuming that the number of visited nodes is known in advance. We describe a tabu search algorithm with multiple neighborhoods, and we test its performance by running it on instances based on TSPLIB. We conclude that the tabu search algorithm finds good-quality solutions fast, even for large instances.
Cite as

Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, and Pieter Vansteenwegen. Heuristics for the Traveling Repairman Problem with Profits. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 34-44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{dewilde_et_al:OASIcs.ATMOS.2010.34,
  author =	{Dewilde, Thijs and Cattrysse, Dirk and Coene, Sofie and Spieksma, Frits C. R. and Vansteenwegen, Pieter},
  title =	{{Heuristics for the Traveling Repairman Problem with Profits}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{34--44},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.34},
  URN =		{urn:nbn:de:0030-drops-27489},
  doi =		{10.4230/OASIcs.ATMOS.2010.34},
  annote =	{Keywords: Traveling Repairman, Profits, Latency, Tabu Search, Relief Efforts}
}
  • Refine by Author
  • 3 Spieksma, Frits C. R.
  • 2 Coene, Sofie
  • 1 Cattrysse, Dirk
  • 1 Dewilde, Thijs
  • 1 Erlebach, Thomas
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Approximation algorithms

  • Refine by Keyword
  • 1 Latency
  • 1 Profits
  • 1 Relief Efforts
  • 1 Tabu Search
  • 1 Traveling Repairman
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2010
  • 1 2011
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact