论文标题
统治者滚动
Ruler Rolling
论文作者
论文摘要
在CCCG '21上，O'Rourke提出了Hopcroft，Josephs and Whitesides的变体'（1985）NP-Complete问题{\ sc Ruler折叠}，他称其为{\ sc luner包装}，并且所有折叠都必须在相同方向上为180度。 Gagie，Saeidi和Sapucaia（2023）指出，如果尺子的最后一个连续部分必须是最长的，那么{\ sc统治者包装}等同于将一串正整数划分为其总和增加的子字符串，以至于最终的子额度额度为最多给定量。他们给出了有或没有此假设的{\ sc luner包装}版本的线性时间算法。在现实生活中，我们不能反复沿同一方向折叠180度的木匠统治者。在本文中，我们提出了{\ sc luler滚动}的更现实的问题，在该问题中，我们在同一方向上反复折叠90度的段，从而将尺子折叠成矩形而不是将其折叠成一个间隔。我们应该报告所有帕累托最佳的滚动。我们注意到，如果尺子的最后一台必须比第三阶段的最后一部分要长得持久 - 类似于Gagie等人的假设 - 那么{\ sc luler rolling}等同于将一串正整数划分为子字符串中的子字符串，以使得偶数子字的总和增加了，就像奇数奇数子的总和一样增加。我们给出了一种简单的动态编程算法，该算法在此假设下报告了二次时间中所有帕累托最佳滚动。即使没有假设，我们的算法仍然可以正常工作，但是随后我们将拥有二维可行解决方案数量的二维解决方案，因此找到帕累托最佳的解决方案，并通过对数因素增加了我们的运行时间。但是，如果我们的目标功能很好，我们仍然使用二次时间。
At CCCG '21 O'Rourke proposed a variant of Hopcroft, Josephs and Whitesides' (1985) NP-complete problem {\sc Ruler Folding}, which he called {\sc Ruler Wrapping} and for which all folds must be 180 degrees in the same direction. Gagie, Saeidi and Sapucaia (2023) noted that if the last straight section of the ruler must be longest, then {\sc Ruler Wrapping} is equivalent to partitioning a string of positive integers into substrings whose sums are increasing such that the last substring sums to at most a given amount. They gave linear-time algorithms for the versions of {\sc Ruler Wrapping} both with and without this assumption. In real life we cannot repeatedly fold a carpenter's ruler 180 degrees in the same direction. In this paper we propose the more realistic problem of {\sc Ruler Rolling}, in which we repeatedly fold the segments 90 degrees in the same direction and thus fold the ruler into a rectangle instead of into an interval. We should report all the Pareto-optimal rollings. We note that if the last straight section of the ruler must be longer than the third to last -- analogously to Gagie et al.'s assumption -- then {\sc Ruler Rolling} is equivalent to partitioning a string of positive integers into substrings such that the sums of the even substrings are increasing, as are the sums of the odd substrings. We give a simple dynamic-programming algorithm that reports all the Pareto-optimal rollings in quadratic time under this assumption. Our algorithm still works even without the assumption, but then we are left with a quadratic number of two-dimensional feasible solutions, so finding the Pareto-optimal ones and increases our running time by a logarithmic factor. If we have a nice objective function, however, we still use quadratic time.
