Abstract
We introduce the online Set Aggregation Problem, which is a natural generalization of the Multi-Level Aggregation Problem, which in turn generalizes the TCP Acknowledgment Problem and the Joint Replenishment Problem. We give a deterministic online algorithm, and show that its competitive ratio is logarithmic in the number of requests. We also give a matching lower bound on the competitive ratio of any randomized online algorithm.
R. A. Carrasco—Supported in part by Fondecyt Project Nr. 1151098.
K. Pruhs—Supported in part by NSF grants CCF-1421508 and CCF-1535755, and an IBM Faculty Award.
C. Stein—Supported in part by NSF grant CCF-1421161.
J. Verschae—Supported in part by Nucleo Milenio Información y Coordinación en Redes ICM/FIC CODIGO RC130003, and Fondecyt Project Nr. 11140579.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
We remark that this definition does not yield monotone service costs. However this does not cause any trouble. Indeed, if two sets \(S_1\subseteq S_2\) fulfill \(C(S_2)< C(S_1)\), then the algorithm can simply serve \(S_2\) instead of \(S_1\) without increasing its cost and without affecting feasibility. Hence, any instance with service cost C can be turned to an equivalent instance with non-decreasing service cost \(C'(S)= \min _{T\supseteq S} C(T)\).
References
Bienkowski, M., Böhm, M., Byrka, J., Chrobak, M., Dürr, C., Folwarcznỳ, L., Jez, L., Sgall, J., Thang, N.K., Veselỳ, P.: Online algorithms for multi-level aggregation. In: European Symposium on Algorithms, pp. 12:1–12:17 (2016)
Buchbinder, N., Feldman, M., Naor, J.S., Talmon, O.: O(depth)-competitive algorithm for online multi-level aggregation. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1235–1244 (2017)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998)
Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478–488 (1993)
Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255–267 (1994)
Bienkowski, M., Böhm, M., Byrka, J., Chrobak, M., Dürr, C., Folwarcznỳ, L., Jeż, L., Sgall, J., Thang, N.K., Veselỳ, P.: Online algorithms for multi-level aggregation. arXiv preprint arXiv:1507.02378 (2015)
Aggarwal, A., Park, J.K.: Improved algorithms for economic lot sizing problems. Oper. Res. 41, 549–571 (1993)
Dooly, D.R., Goldman, S.A., Scott, S.D.: On-line analysis of the TCP acknowledgment delay problem. J. ACM 48(2), 243–273 (2001)
Karlin, A.R., Kenyon, C., Randall, D.: Dynamic TCP acknowledgement and other stories about e/(e\(\,-\,\)1). Algorithmica 36(3), 209–224 (2003)
Bienkowski, M., Byrka, J., Chrobak, M., Jeż, Ł., Nogneng, D., Sgall, J.: Better approximation bounds for the joint replenishment problem. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 42–54 (2014)
Buchbinder, N., Kimbrel, T., Levi, R., Makarychev, K., Sviridenko, M.: Online make-to-order joint replenishment model: primal-dual competitive algorithms. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 952–961 (2008)
Bienkowski, M., Byrka, J., Chrobak, M., Dobbs, N., Nowicki, T., Sviridenko, M., Świrszcz, G., Young, N.E.: Approximation algorithms for the joint replenishment problem with deadlines. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7965, pp. 135–147. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39206-1_12
Badrinath, B., Sudame, P.: Gathercast: the design and implementation of a programmable aggregation mechanism for the internet. In: International Conference on Computer Communications and Networks, pp. 206–213 (2000)
Bortnikov, E., Cohen, R.: Schemes for scheduling of control messages by hierarchical protocols. In: Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 865–872 (1998)
Hu, F., Cao, X., May, C.: Optimized scheduling for data aggregation in wireless sensor networks. In: International Conference on Information Technology: Coding and Computing (ITCC 2005), vol. 2, pp. 557–561 (2005)
Yuan, W., Krishnamurthy, S., Tripathi, S.: Synchronization of multiple levels of data fusion in wireless sensor networks. In: Global Telecommunications Conference, vol. 1, pp. 221–225 (2003)
Papadimitriou, C.H.: Computational aspects of organization theory. In: Diaz, J., Serna, M. (eds.) ESA 1996. LNCS, vol. 1136, pp. 559–564. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61680-2_82
Crowston, W.B., Wagner, M.H.: Dynamic lot size models for multi-stage assembly systems. Manag. Sci. 20(1), 14–21 (1973)
Kimms, A.: Multi-level lot sizing and scheduling: methods for capacitated, dynamic, and deterministic models. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-642-50162-3
Lambert, D.M., Cooper, M.C.: Issues in supply chain management. Ind. Mark. Manag. 29(1), 65–83 (2000)
Becchetti, L., Marchetti-Spaccamela, A., Vitaletti, A., Korteweg, P., Skutella, M., Stougie, L.: Latency-constrained aggregation in sensor networks. ACM Trans. Algorithms 6(1), 13:1–13:20 (2009)
Pedrosa, L.L.C.: Private communication (2013)
Levi, R., Roundy, R., Shmoys, D.B.: Primal-dual algorithms for deterministic inventory problems. Mathematics of Operations Research 31(2), 267–284 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Detailed Proofs
A Detailed Proofs
In this section we detail some of the proofs from Sect. 3.
Lemma 1. There exists a proactive schedule whose objective value is at most twice optimal.
Proof
We show how to iteratively transform an arbitrary schedule \(\mathcal {Z}\) into a proactive schedule in such a way that the total cost at most doubles. Let t be the next time in \(\mathcal {Z}\) when there is an unserved set S, with the property that the waiting time for S, infinitesimally after t, is greater than the service cost for S. We then add the set S at time t to \(\mathcal {Z}\). The service cost of this set is at most the total waiting time of the requests that it serves. Thus the total service cost of the final schedule is at most the waiting time in the original \(\mathcal {Z}'\). Further the transformation can only decrease the total waiting cost, since the requests in S are being served no later than they were originally.
Lemma 2. The value \(\text {LB}^-(s, t, d)\) and \(\text {LB}^+(s, t, d)\) are monotone on the set of requests, that is, adding more requests between times s and t can not decrease either. Moreover, \(\text {LB}^-(s, t, d)\) and \(\text {LB}^+(s, t, d)\) are non-decreasing as a function of t and as a function of d, for any \(s\le t\le d\).
Proof
Any schedule that is proactive for the larger set of requests is also proactive for the smaller set of requests, because the waiting time of the requests serviced can not be more in the smaller set of requests than in the larger set of requests. The monotonicity on t follows directly from the monotonicity on the set of requests. The monotonicity on d is clear since for any \(d\le d'\), a proactive solution up to time \(d'\) is also proactive up to time d.
Lemma 3. Assume that RetrospectiveCover just computed a new deadline d[i] in line 7. Then process i will either reach a new milestone or be terminated by time d[i].
Proof
If d[i] is infinite, then this is obvious, so assume otherwise. If process i is terminated before time d[i] then this is obvious, so assume otherwise. If no requests arrive during the time interval (m[i], d[i]) then process i will reach a new milestone exactly at time d[i] by the definition of milestones. If requests arrive before d[i] then the claim follows by the monotonicity of \(\text {LB}^+\), see Lemma 2.
Lemma 5. It holds that \( \sum _{j=1}^{k-1} x_j \le x_0\).
Proof
First notice that \(\text {LB}^{-}(u_{-1},t,t)\le 2\text {LB}^{+}(u_{-1},u_0,u_0)=2x_0\), since otherwise process i would have hit a milestone within the interval \((u_{0},t)\). Then, it suffices to show that \( \sum _{j=0}^{k-1} x_j\le \text {LB}^{-}(u_{-1},t,t)\). To show this last bound, fix \(j\in \{0,\ldots ,k-1\}\) and consider a proactive schedule \(\mathcal {Z}\) for requests arriving in \((u_{-1},t)\). Within each interval \((u_{j-1},u_j)\), the solution is proactive when considering requests with release date in \((u_{j-1},u_j]\), and hence the serving cost of the requests served by \(\mathcal {Z}\) within this interval is at most \(\text {LB}^+(u_{j-1},u_{j-1},u_j)\). We remark that this is also true for \(j=k-1\) as \(u_{k-1}<t\). Taking \(\mathcal {Z}\) minimizing the service cost within \((u_{-1},t)\), we obtain the required bound, \( \sum _{j=0}^{k-1} x_j\le \text {LB}^{-}(u_{-1},t,t)\).
Lemma 6. For any set S serviced at time t in the schedule produced by the algorithm RetrospectiveCover, it will be the case that \( \mathop { W _t}(S) \le 2 \mathop { C }(S)\).
Proof
Assume that a process i hit a milestone at time t. We adopt the notation from Subsubsect. 3.3.1 and illustrated in Fig. 1. Additionally let \(U_j\) be the requests that are released in the time interval \((u_{j-1}, u_j)\) for \(j \in \{0,1,\ldots , k\}\).
We now prove that the sets serviced in line 5 have waiting time at most twice the service cost. Also, we show that after serving such sets, the set \(\cup _{h=k-j}^k U_h\) has no violated subset at time t, where \(j=a-\ell \). We show this by induction on \(j=a-\ell \). The base case is when \(j=0\) (\(\ell =a\)). There is no violated subset of \(U_k\) at time t since process \(i + k=a\) did not hit a milestone before time t. Thus, no set serviced in \(\text {LB}^-(s[a], t, t)\) is violated. Obviously, after servicing such sets, \(U_k\) still has no violated subset. Now let us show the two properties for an arbitrary j. By induction hypothesis, the set \(\cup _{h=k-(j-1)}^k U_h\) has no violated subset at time t. There is no violated subset of \(U_{k-j}\) at time t since the servicing of sets in \(\text {LB}^-(s[a- j], m[a-j], d[a-j])=\text {LB}^-(u_{k- j - 1}, u_{k-j}, d[a-j])\) at time \(m[a-j]\) guaranteed that \(U_{k-j}\) would not have any violated subsets until after time \(d[a-j]\) and \(t \le d[a-j]\). Thus no set serviced in \(\text {LB}^-(s[a-j], t, t)\) in line 5 has waiting time at most twice the service cost. Further since \(\text {LB}^-(s[a-j], t, t)=\text {LB}^-(u_{k-j-1}, t, t)\) is a proactive schedule, after serving sets in such solution the set \(\cup _{h=k-j}^k U_h\) has no violated subset at time t.
Finally the same argument can be applied to the sets serviced in line 8 in RetrospectiveCover.
Theorem 2. The RetrospectiveCover algorithm is \(O(\log |R|)\)-competitive.
Proof
Applying Lemma 4 to the original process, and noting that the service cost in the final invocation of line 8 is at most twice the previous service costs, one obtains that the service cost for the algorithm is \(O(\log |R|)\) times the lower bound. By Lemma 1 the lower bound is at most twice the optimal, and by Lemma 6 the waiting cost for requests serviced by the algorithm is at most the service cost of these requests. Finally the waiting cost of any unserviced requests is at most twice the service cost of the algorithm.
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Carrasco, R.A., Pruhs, K., Stein, C., Verschae, J. (2018). The Online Set Aggregation Problem. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)