Kimball Martin ; Krishnan Shankar - How often should you clean your room?

dmtcs:2109 - Discrete Mathematics & Theoretical Computer Science, June 29, 2015, Vol. 17 no. 1 - https://doi.org/10.46298/dmtcs.2109
How often should you clean your room?Article

Authors: Kimball Martin 1; Krishnan Shankar 1

  • 1 Department of Mathematics [Norman]

Analysis of Algorithms

[en]
We introduce and study a combinatorial optimization problem motivated by the question in the title. In the simple case where you use all objects in your room equally often, we investigate asymptotics of the optimal time to clean up in terms of the number of objects in your room. In particular, we prove a logarithmic upper bound, solve an approximate version of this problem, and conjecture a precise logarithmic asymptotic.

https://doi.org/10.46298/dmtcs.2109
Source: HAL:hal-01196853v1
Volume: Vol. 17 no. 1
Section: Analysis of Algorithms
Published on: June 29, 2015
Imported on: January 10, 2015
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] search with cleanup, combinatorial optimization, coupon collector’s problem, sequential occupancy, Stirling numbers of the second kind
Funding:
    Source : OpenAIRE Graph
  • Rigidity theorems in geometry and topology; Funder: National Science Foundation; Code: 1104352

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Publications

Has review
  • 1 zbMATH Open

Share and export

Consultation statistics

This page has been seen 816 times.
This article's PDF has been downloaded 830 times.