Learning-Augmented Algorithms for the Bahncard Problem

Authors: hailiang  zhao
xueyan  tang
peng  chen
shuiguang  deng
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:53:58

Abstract: In this paper, we study learning-augmented algorithms for the Bahncard problem. The Bahncard problem is a generalization of the ski-rental problem, where a traveler needs to irrevocably and repeatedly decide between a cheap short-term solution and an expensive long-term one with an unknown future. Even though the problem is canonical, only a primal-dual-based learning-augmented algorithm was explicitly designed for it. We develop a new learning-augmented algorithm, named PFSUM, that incorporates both history and short-term future to improve online decision making. We derive the competitive ratio of PFSUM as a function of the prediction error and conduct extensive experiments to show that PFSUM outperforms the primal-dual-based algorithm.

Main paper: 
 introduction: 
 The Bahncard is a railway pass of the German railway company, which provides a discount on all train tickets for a fixed time period of pass validity. When a travel request arises, a traveler can buy the train ticket with the regular price, or purchase a Bahncard first and get entitled to a discount on all train tickets within its valid time. The Bahncard problem is an online cost minimization problem, whose objective is to minimize the overall cost of pass and ticket purchases, without knowledge of future travel requests [1] . It reveals a recurring renting-or-buying phenomenon, where an online algorithm needs to irrevocably and repeatedly decide between a cheap short-term solution and an expensive long-term one with an unknown future. The performance of an online algorithm is typically measured by the competitive ratio, which is the worst-case ratio across all inputs between the costs of the online algorithm and an optimal offline one [2] .Recently, there has been growing interest in using machine-learned predictions to improve online algorithms. One seminal work was done by Lykouris and Vassilvtiskii [3] for the caching problem, in which the online algorithms are allowed to leverage predictions of future inputs to make decisions, but they are not given any guarantee on the prediction accuracy. Since then, the framework of online algorithms with predictions has been extensively studied for a wide range of problems including ski-rental [4] [5] [6] [7] [8] , scheduling [9, 10] , graph optimization [11] , covering [12, 13] , data structures [14] [15] [16] , etc. In this framework, the measurements for the online algorithms include consistency and robustness, where the former refers to the competitive ratio under perfect predictions while the latter refers to the upper bound of the competitive ratio when the predictions can be arbitrarily bad.The Bahncard problem with machine-learned predictions was recently studied by Bamas et al. [12] . They designed a primal-dual-based algorithm assuming given a prediction of the optimal solution, i.e., an optimal collection of times to purchase Bahncards such that the total cost is minimized. While Bamas et al. [12] presented an elegant framework for seamlessly integrating the primal-dual method with a predicted solution, their approach faces three critical issues. First, their considered scenario is limited, involving slotted time and a fixed ticket price of 1 for any travel request. The discretization is necessary for them to formulate an integer program and enable the application of the primal-dual method proposed by Buchbinder et al. [17] . Second, their results of consistency and robustness are weak in that they only hold under the condition that the cost of a Bahncard goes towards infinity, in which case the optimal solution is to never buy any Bahncard. Last, their algorithm demands a complete solution as input advice, which implies a predicted complete sequence of travel requests over an arbitrarily long timespan, which is impractical for real employment.In this paper, we study the Bahncard problem with machine-learned predictions, adopting a different technical perspective. We address the general scenario where travel requests may arise at any time with diverse ticket prices. We develop an algorithm, named PFSUM, which takes short-term predictions on future trips as inputs. We derive its competitive ratio under any prediction error that is naturally defined as the difference between the predicted and true values. To present our results, we introduce several notations. The Bahncard problem is instantiated by three parameters and denoted by BP(C, β, T ), meaning that a Bahncard costs C, reduces any (regular) ticket price p to βp for some 0 ≤ β < 1, and is valid for a time period of T . When β = 0 and T → ∞, the Bahncard problem reduces to the well-known ski-rental problem. Following the definition in [3, 4] , we take the competitive ratio of a learning-augmented online algorithm ALG as a function CR ALG (η) of the prediction error η. ALG is δ-consistent if CR ALG (0) = δ, and ϑ-robust if CR ALG (η) ≤ ϑ for all η.At any time t when a travel request arises and there is no a valid Bahncard, a prediction on the total (regular) ticket price of all travel requests in the upcoming interval [t, t + T ) is made. Incorporating this prediction, PFSUM purchases a Bahncard at time t when (i) the total ticket price in the past interval (t -T, t] is at least γ and (ii) the predicted total ticket price in [t, t + T ) is also at least γ, where γ := C/(1β). Denoting by η the maximum prediction error, we derive thatEQUATIONThe result shows that PFSUM is 2/(1 + β)-consistent and 1/β-robust, and its competitive ratio degrades smoothly as the prediction error increases. We also share our experience in the design of PFSUM with some interesting observations. 
related work: 
 The Bahncard problem. Fleischer [1] was the first to study the Bahncard problem. By extending the optimal 2-competitive break-even algorithm for ski-rental, he proposed an optimal (2β)competitive deterministic algorithm named SUM for BP(C, β, T ). He also proposed a randomized algorithm named RAND for BP(C, β, ∞), and proved that it is e/(e -1 + β)-competitive. He conjectured that RAND keeps the same competitiveness for T < ∞. Karlin et al. [18] designed a randomized online algorithm for TCP acknowledgement and applied it to BP(C, β, T ) with the conjecture settled positively. In addition, the Bahncard problem was extended to several realistic problems in computer systems such as bandwidth cost minimization [19] , cloud instance reservation [20] , and data migration [21] . Notably, Wang et al. [20] designed algorithms incorporating short-term predictions about the future for reserving virtual machine instances in clouds, which brings inspiration to our algorithm design.Learning-augmented algorithms. Learning-augmented algorithms aim to leverage machine-learned predictions to improve the performance in both theory and practice [22] . Algorithms using possibly imperfect predictions have found applications in numerous important problems [4-7, 9-11, 16, 23-27] . See https://algorithms-with-predictions.github.io/ for a comprehensive collection of the literature.To our knowledge, the only learning-augmented algorithms specifically designed for the Bahncard problem were developed by Bamas et al. [12] and Drygala et al. [28] . Bamas et al. [12] proposed an algorithm, named PDLA, which is λ/(1-β+λβ)•(e λ -β)/(e λ -1)-consistent and (e λ -β)/(e λ -1)robust when C → ∞, where λ ∈ (0, 1] is a hyper-parameter of the algorithm. Their method, as previously discussed, is limited to scenarios with slotted time and uniform ticket prices for all travel requests. Our approach significantly differs from [12] . First, we address the general scenario where travel requests can arise at any time and feature varied ticket prices. Second, our algorithm utilizes short-term predictions provided at the times when travel requests are made, in contrast to their method which requires predicting a complete solution. We experimentally compare our algorithm with that of [12] in Section 5. Drygala et al. [28] focused on how many predictions are required to gather enough information to output a near-optimal Bahncard purchasing schedule, assuming all predictions are correct. The learning-augmented algorithm proposed takes a suggested sequence of buying times as input and assumes a slotted time setting, thereby sharing similar drawbacks to [12] .Im et al. [26] explored a somewhat related TCP acknowledgement problem with machine-learned predictions. They introduced a new prediction error measure designed to assess how much the optimal objective value changes as the difference between actual requests and predicted requests varies. A detailed comparison between our work and [26] is provided in Appendix A.1 of [29] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [No] Justification: This paper provides both theoretical and experimental contributions for PF-SUM. The theoretical results are derived without strong assumptions, but the experimental results are conducted, although extensively, only on synthesized dataset. Different travel request patterns may influence the advantage of PFSUM over the other algorithms.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 We adhere to the notations coined by Fleischer [1] . BP(C, β, T ) with C > 0, T > 0, and 0 ≤ β < 1 is a request-answer game between an online algorithm ALG and an adversary (see, e.g., [30] ). The adversary presents a finite sequence of travel requests σ = σ 1 σ 2 • • • , where each σ i is a tuple (t i , p i ) that contains the travel time t i ≥ 0 and the regular ticket price p i ≥ 0. The travel requests are presented in chronological order:0 ≤ t 1 < t 2 < • • • .ALG needs to react to each travel request σ i . If ALG does not have a valid Bahncard, it can opt to buy the ticket with the regular price p i , or first purchase a Bahncard which costs C, and then pay the ticket price with a β-discount, i.e., βp i . A Bahncard purchased at time t is valid during the time interval [t, t + T ). Note that a travel request arising at time t + T does not benefit from the Bahncard purchased at time t. We say σ i is a reduced request of ALG if ALG has a valid Bahncard at time t i . Otherwise, σ i is a regular request of ALG. We use ALG(σ i ) to denote ALG's cost on σ i :ALG(σ i ) = βp i ALG has a valid Bahncard at t i , p i otherwise.We denote by ALG(σ) the total cost of ALG for reacting to all the travel requests in σ. The competitive ratio of ALG is defined by CR ALG := max σ ALG(σ)/OPT(σ), where OPT is an optimal offline algorithm for BP(C, β, T ). We use ALG(σ; I) to denote the partial cost incurred during a time interval I: ALG(σ; I) = C •x+ i:ti∈I ALG(σ i ), where x is the number of Bahncards purchased by ALG in I. Additionally, we use c(σ; I) to denote the total regular cost in I: c(σ; I) := i:ti∈I p i . Given a time length l, we define the l-recent-cost of σ at time t as c(σ; (tl, t]). Similarly, we define the l-future-cost of σ at time t as c(σ; [t, t + l)). In our design, we assume that when a travel request (t, p) arises, a short-term prediction of the total regular cost in the time interval [t, t + T ) can be made.To represent prediction errors, we use ĉ(σ; [t, t + T )) to denote the predicted total regular cost in [t, t + T ). Sometimes we are concerned about the regular requests of an algorithm ALG in a recent time interval. Thus, we further define the regular l-recent-cost of ALG on σ at time t asALG r σ; (t -l, t] := i:σi is a regular request of ALG in (t-l,t] p i .Without loss of generality, we assume that an online algorithm ALG or an optimal offline algorithm OPT considers purchasing Bahncards at the times of regular requests only. The rationale is that the purchase of a Bahncard at any other time can always be delayed to the next regular request without increasing the total cost.4 Learning-Augmented Algorithms for the Bahncard Problempaper. Additionally, for the results, we have given 95% confidence intervals for all results of 100 experiments through the shaded area in the figures. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.  
initial attempt: 
 The SUM algorithm developed in [1] purchases a Bahncard based on the cost incurred in the past only. It is likely that there is no further travel request in the valid time of the Bahncard besides the request at the purchasing time. Our initial attempt is an adaptation of the A w γ algorithm proposed in [20] . Aiming to save cost, the A w γ algorithm shifts the cost consideration for Bahncard purchasing towards the future with the help of predictions. That is, a Bahncard is purchased based on a combination of the actual cost incurred in the past and the predicted cost in the future. We name the adaptation of A w γ to the Bahncard problem as SUM w . 1 Specifically, at each regular request (t, p), SUM w predicts the total regular cost in a prediction window (t, t + w] where w (0 < w < T ) is the length of the prediction window. SUM w purchases a Bahncard at a regular request (t, p) whenever the sum of the regular (Tw)-recent-cost at t and the predicted total regular cost in (t, t + w] is at least γ, i.e., SUM r w σ;EQUATIONNote that SUM w reduces to SUM when w = 0.Unfortunately, SUM w is not a good algorithm for using machine-learned predictions. We find that its consistency is at least (3β)/(1 + β), which is even larger than SUM's competitive ratio of 2β since β < 1. We construct a travel request sequence to show the consistency result in Appendix A. SUM w fails because if a Bahncard is purchased at time t, it is possible that most of the ticket cost in the interval (t + w -T, t + w] is incurred before t. Consequently, only a small fraction of the ticket cost is incurred from t onward and can benefit from the Bahncard purchased. As a result, SUM w suffers from the same deficiency as SUM. We remark that it is not helpful to set the prediction window length w to T or even larger values, because the travel request arising at (or beyond) time t + T (if any) is not covered by the Bahncard purchased at time t.What we have learned from SUM w is that the Bahncard purchase condition should not be based on the total ticket cost in a past time interval and a future prediction window. Thus, our second algorithm FSUM (Future SUM) is designed to purchase a Bahncard at a regular request (t, p) whenever the predicted T -future-cost at time t is at least γ, i.e.,EQUATIONNote that FSUM ̸ = SUM T because the Bahncard purchase condition ofSUM T is ĉ σ; (t, t+T ] ≥ γ. Theorem 4.1. FSUM is 2/(1 + β)-consistent.The proof is given in Appendix A.3 of [29] . FSUM's consistency is generally better than SUM's competitive ratio since 2/(1 + β) < 2β always holds for 0 < β < 1. However, similar to SUM w , FSUM does not have any bounded robustness. Consider again the example where only one travel request (t, p) arises with p → 0, but the predictor yields ĉ(σ; [t, t + T )) ≥ γ. Then, FSUM purchases a Bahncard at (t, p) and FSUM(σ)/OPT(σ) = (C + βp)/p → ∞.FSUM fails to achieve any bounded robustness because it completely ignores the historical information in the Bahncard purchase condition. Thus, the worst case is that the actual ticket cost in the prediction window is close to 0, while the predictor forecasts that it exceeds γ, in which case hardly anything benefits from the Bahncard purchased. On the other hand, we note that SUM achieves a decent competitive ratio because a Bahncard is purchased only when the regular T -recent-cost is at least γ, so that the Bahncard cost can be charged to the regular T -recent-cost in the competitive analysis. Motivated by this observation, we introduce a new algorithm PFSUM (Past and Future SUM), in which the Bahncard purchase condition incorporates the ticket costs in both a past time interval and a future prediction window, but uses them separately rather than taking their sum. PFSUM purchases a Bahncard at a regular request (t, p) whenever (i) the T -recent-cost at t is at least γ, i.e., c(σ; (t -T, t]) ≥ γ, and (ii) the predicted T -future-cost at t is also at least γ, i.e., ĉ(σ; [t, t + T )) ≥ γ. Note that the first condition is different from the condition for SUM to purchase a Bahncard: PFSUM considers the T -recent-cost, but SUM considers only the regular T -recent-cost. The rationale is that by definition, the regular T -recent-cost is not covered by any Bahncard, so requiring it to be at least γ for Bahncard purchase would make the algorithm less effective in saving cost. Compared with FSUM, though PFSUM has an additional condition for purchasing the Bahncard, it is somewhat surprising that PFSUM achieves the same consistency of 2/(1 + β) as FSUM, as shown below.Given a travel request sequence σ, we use µ 1 < • • • < µ m to denote the times when PFSUM purchases Bahncards. Accordingly, the timespan can be divided into epochs E j := [µ j , µ j+1 ) for 0 ≤ j ≤ m, where we define µ 0 = 0 and µ m+1 = ∞. Each epoch E j (except E 0 ) starts with an on phase [µ j , µ j + T ) (the valid time of the Bahncard purchased by PFSUM), followed by an off phase [µ j + T, µ j+1 ) (in which there is no valid Bahncard by PFSUM). Epoch E 0 has an off phase only.We define η as the maximum prediction error among all the predictions used by PFSUM:EQUATIONThen, for any travel request (t, p) in an off phase, we haveEQUATIONThe following lemmas will be used frequently in the competitive analysis of PFSUM. Lemma 4.2. The total regular cost in an on phase is at least γη.Proof. If c(σ; [µ j , µ j + T )) < γη for some j, it follows from (5) that ĉ(σ; [µ j , µ j + T )) ≤ c(σ; [µ j , µ j + T )) + η < γη + η = γ, which means that PFSUM would not purchase a Bahncard at time µ j , leading to a contradiction. Thus, we must have c(σ; [µ j , µ j + T )) ≥ γη.Lemma 4.3. In an off phase, the total regular cost in any time interval [t, t + l) of length l ≤ T is less than 2γ + η.Proof. Assume on the contrary that c(σ; [t, t + l)) ≥ 2γ + η. We take the earliest travel request Proof. Assume on the contrary that s 2 + s 3 + s 4 > 2γ + η. Then, s 3 > 0 and hence there is at least one travel request during the off phase. We take the earliest travel request (t ′ , p) in the off phase, such that c(σ; [t, t ′ ]) ≥ γ. With a similar analysis to Lemma 4.3, we can derive that PFSUM should purchase a Bahncard at time t ′ , contradicting that t ′ is in the off phase.(t ′ , p) in [t, t + l) such that c(σ; [t, t ′ ]) ≥ γ. This implies c(σ; [t, t ′ )) < γ. Then, we have c(σ; [t ′ , t + l)) = c(σ; [t, t + l)) -c(σ; [t, t ′ )) > 2γ + η -γ = γ + η. Hence, c(σ; (t ′ -T, t ′ ]) ≥ c(σ; [t, t ′ ]) ≥ γ and c σ; [t ′ , t ′ + T ) ≥ c(σ; [t ′ , t + l)) > γ + η. By (5), the latter further leads to ĉ(σ; [t ′ , t ′ + T )) ≥ c(σ; [t ′ , t ′ + T )) -η > γ,We adopt a divide-and-conquer approach to analyze PFSUM. Specifically, we focus on the time intervals in which at least one of PFSUM and OPT has a valid Bahncard, and analyze the cost ratio between PFSUM and OPT in these intervals. Consider a maximal contiguous time interval throughout which at least one of PFSUM and OPT has a valid Bahncard. As shown in Figure 2 , there are 6 different patterns. If OPT and PFSUM purchase a Bahncard at the same time, the time interval is exactly an on phase (Pattern I), and the cost ratio in it is 1 (Proposition 4.5). Otherwise, there are 5 different cases: the time interval does not overlap with any on phase (Pattern II); and the time interval overlaps with at least one on phase -it can start at some time in an on or off phase and end at some time in an on or off phase, giving rise to four cases (Patterns III to VI). In Patterns II to VI, we assume that none of the involved Bahncards purchased by OPT are bought at the same time as any Bahncards purchased by PFSUM. x ≥ 1… … … … … … … … … … … … … … … τ i τ i+x+1 + T τ i µ j+x µ j+x + T µ j τ i+x τ i+x + T µ j µ j+x µ j+x + T µ j µ j + T τ i τ i + T τ i+x+1Bahncard valid time by OPT … EQUATIONApparently, if the cost ratios between PFSUM and OPT of Patterns II to VI are all capped by the same bound, the competitive ratio of PFSUM is given by this bound. Unfortunately, this is not exactly true. In what follows, we show that the cost ratios of Patterns II to V can be capped by the same bound (Propositions 4.6 and 4.7), which is the competitive ratio of PFSUM that we would like to prove. For Pattern VI, we show that its cost ratio is capped by the same bound if a particular condition holds, where we refer to such Pattern VI as augmented Pattern VI (Proposition 4.8). For non-augmented Pattern VI, we show that it must be accompanied by Patterns I to IV in the sense that a time interval of non-augmented Pattern VI must be preceded (not necessarily immediately) by a time interval of Pattern I, II, III or IV. We prove that the cost ratio of non-augmented Pattern VI combined with such Pattern I, II, III or IV is capped by the same aforesaid bound (Propositions 4.9 and 4.10). This then concludes that PFSUM's competitive ratio is given by this bound. Proposition 4.6. (Pattern II) If OPT purchases a Bahncard at time τ i in the off phase of an epoch E j and the Bahncard expires in the same off phase, i.e., µ j + T ≤ τ i < τ i + T < µ j+1 , thenEQUATIONProof. Let x = c(σ; [τ i , τ i +T )). Based on the definition of Pattern II, OPT(σ; [τ i , τ i +T )) = C+βx (OPT buys a card at τ i ) and PFSUM(σ; [τ i , τ i + T )) = x (PFSUM does not buy cards during any off phase). Hence, the cost ratio is x C+βx , which increases with x since β < 1. By Lemma 4.3, x < 2γ + η. Thus, the cost ratio is bounded by 2γ+ηC+β(2γ+η) = 2γ+η (1-β)γ+β(2γ+η) = 2γ+η (1+β)γ+βη .The proof technique of the following propositions for Patterns III to VI is to divide the time interval concerned into sub-intervals, where each sub-interval starts and ends at the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased expires. Then, for 0 ≤ η ≤ γ and η > γ, we respectively derive the upper bound of the cost ratio based on Lemmas 4.2 to 4.4. All the bounds in Propositions 4.7 to 4.8 are tight (achievable). Detailed proofs are given in Appendixes A.4 to A.5 of [29] . Proposition 4.7. (Patterns III to V) The cost ratio in the time interval of Patterns III, IV, and V is bounded byEQUATION)We We remark that the cost ratio of general Pattern VI cannot be capped by the same bound as Patterns III to V. This is because in Pattern VI, PFSUM purchases one more Bahncard than OPT and hence has a higher cost of card purchases, whereas PFSUM purchases less or equal numbers of Bahncards compared to OPT in Patterns III to V. Thus, an additional condition is necessary in Proposition 4.8.Next, we examine non-augmented Pattern VI. Note that the time intervals of Patterns V and VI cannot exist in isolation. By the definition of PFSUM, when a Bahncard is purchased at time µ j , the total regular cost in the preceding interval (µ j -T, µ j ] is at least γ (referred to as feature ⋄). Consequently, by Lemma 3.1, OPT must purchase a Bahncard whose valid time overlaps with (µ j -T, µ j ]. To deal with non-augmented Pattern VI that starts at time µ j for some j, we backtrack from µ j to find out what happens earlier. Our target is to identify all possible patterns that might precede Pattern VI. Note that the time interval (µ j -T, µ j ] definitely intersects with the off phase of epoch E j-1 and may also intersect with the on phase of E j-1 (if the off phase of E j-1 is shorter than T ). Therefore, it is possible for all Patterns I to VI to precede Pattern VI (see Figures 3(b ) and (c) for illustrations). If Pattern I, IV or VI precedes Pattern VI, there is an off phase in between, in which neither PFSUM nor OPT holds a valid Bahncard. Figure 3 (a) presents a pattern graph to illustrate all possible concatenations of patterns preceding Pattern VI. In this graph, a node represents a pattern, and an edge from node i to node j means pattern i can precede pattern j. Since every Pattern V or VI must be preceded by some pattern, the backtracking will always encounter a time interval of Pattern I, II, III or IV. We stop backtracking at the first Pattern I, II, III or IV encountered.We use p 1 ⊕ p 2 to denote the composite of pattern p 1 followed by pattern p 2 ; use p y to denote a sequence comprising y consecutive instances of pattern p; and use {p 1 , . . . , p n } ⊕ p j to represent all possible composite patterns of the form p i ⊕ p j for each i = 1, . . . , n. Then, the patterns encountered in the backtracking can be represented byEQUATIONwhere y can be any non-negative integers. Following the feature ⋄, for each VI in {V, VI} y of (9), the total regular cost in the last on phase of Pattern VI and the following off phase is at least γ. It is easy to see that the cost ratio between PFSUM and OPT in the time interval of such Pattern VI is no larger than that of augmented Pattern VI and hence the upper bound given in Proposition 4.8.For each V in {V, VI} y of (9), the cost ratio of Pattern V is capped by the same bound based on Proposition 4.7. In the following, we prove that the cost ratio of non-augmented Pattern VI combined with Pattern I, II, III or IV at the beginning of ( 9) is also capped by the same bound. Proposition 4.9. The cost ratio in the combination of a time interval of Pattern VI and a time interval of Pattern II or III is bounded by (8) . Proof Sketch. Consider Pattern IV. When analyzing the cost ratio of Pattern IV in Proposition 4.7, it is assumed that the total regular cost in the last on phase is at least γη. In IV of (9), following the feature ⋄, the total cost of travel requests in the last on phase of Pattern IV and the following off phase is at least γ. Thus, there is an additional cost of at least η. Therefore, we can "migrate" an additional cost of η to the non-augmented Pattern VI at the end of ( 9) and make the latter become an augmented Pattern VI so that the result of Proposition 4.8 can be applied. Meanwhile, the proof of Proposition 4.7 still applies to the Pattern IV even if the cost η is removed from the last on phase. Hence, after migrating the cost of η, the Patterns IV and VI involved have the same upper bound of cost ratio given in (8) . The proof for Pattern I is similar. See Appendix A.7 of [29] for details.ProofBy the above analysis and Propositions 4.6 to 4.10, we have: Theorem 4.11. PFSUM has a competitive ratio ofEQUATION)By letting η = 0, it is easy to see that the consistency of PFSUM is 2/(1 + β). Note that the competitive ratio of ( 10) is a continuous function of the prediction error η. It increases from 2/(1 + β) to (4β)/(1 + 2β) as η increases from 0 to γ, and further increases from (4β)/(1 + 2β) towards 1/β as η increases from γ towards infinity. Hence, PFSUM is 1/β-robust. 
experiments: 
 We conduct extensive experiments to compare PFSUM with SUM [1] , PDLA [12] , SUM w (Section 4.1), FSUM (Section 4.2), and SRL (Ski-Rental-based Learning algorithm), where SRL is adapted from Algorithm 2 proposed in [4] for ski-rental. SRL performs as follows. Let λ ∈ (0, 1] be a hyper-parameter, SRL purchases a Bahncard at a regular request (t, p) if and only if there exists a time t ′ ∈ (t -T, t] that satisfies one of the following conditions: (i) the predicted T -future-cost at time t ′ is no less than γ, and the total regular cost in [t ′ , t] is greater than λγ; or (ii) the predicted T -future-cost at time t ′ is less than γ, and the total regular cost in [t ′ , t] is greater than γ/λ.We test SUM w with w = T /2, and test SRL and PDLA with λ set to 0.2, 0.5, and 1. To accommodate SRL and PDLA, we discretize time over a sufficiently long timespan, closely approximating a continuous time scenario. The experimental results across diverse input instances demonstrate the superior performance of PFSUM.Input instances. Referring to the experimental setup of [31] , we consider two main types of traveler profiles: commuters, and occasional travelers. We set the timespan at 2000 days, during which commuters travel every day. For occasional travelers, there is a time gap between travel requests. We model the inter-request time of occasional travelers using an exponential distribution with a mean of 2. We consider only one travel request per day. This is because multiple travel requests occurring on the same day can be effectively treated as a single request with combined ticket price, since a Bahncard's validity either covers an entire day or does not cover any part of the day.For each request sequence generated, we investigate three types of ticket price distributions: a Normal distribution with a mean of 50 and a variance of 25, a Uniform distribution centered around a mean of 50, and a Pareto distribution called the Lomax distribution with a shape parameter of 2 and a scale parameter of 50. Our choice of the Pareto distribution stems from the observation that prices of travel requests in the real world often exhibit a heavy tail, which suggests that a minority of travel requests typically account for a significant portion of total cost. Such heavy-tailed distributions are often hypothesized to adhere to some form of Pareto distributions [32, 33] .Noisy prediction. The predictions are generated by adding noise to the original instance, following the methodology used by Bamas et al. [12] . Specifically, we introduce a perturbation probability p.For each day in a given instance, with probability p, the travel request on that day is removed, if it exists. Meanwhile, with probability p, we add random noise, sampled from the same distribution used for generating ticket prices, to the price of the travel request, or simply add a travel request if no request exists on that day. These two operations are executed independently. We vary the perturbation probability from 0 to 1 in the experiments. Intuitively, the prediction error increases with the perturbation probability. The predictions needed by SRL, SUM w , FSUM, and PFSUM are derived from the total regular cost over the specified time period in the perturbed instance. For PDLA, the predicted solution is obtained by executing the offline optimal algorithm on the perturbed instance. We make the following observations from the experimental results. (1) When predictions are good (perturbation probability is small), PFSUM, FSUM, SUM w , and SRL all perform better than SUM. This shows that predictions on the ticket prices of short-term future trips are useful for reducing the total cost. With perfect predictions (perturbation probability = 0), in most cases, either PFSUM or FSUM produces the lowest cost ratio among all algorithms. This empirically confirms that PFSUM and FSUM have better consistency than SUM and SUM w . ( 2) PFSUM outperforms all the other algorithms for a wide range of perturbation probability, demonstrating that PFSUM makes wise use of predictions. In general, PFSUM has the narrowest confidence intervals, indicating that its results are the most stable among all algorithms. (3) For the Pareto distribution, as the prediction error increases, PFSUM demonstrates its robustness through a gradual and smooth rise in the cost ratio to OPT. Even when the perturbation probability is large, PFSUM hardly performs worse than SUM.In contrast, the performance of SUM w and FSUM deteriorates rapidly with increasing perturbation probability, showing their poor robustness. (4) The primal-dual-based algorithm PDLA generally has much higher cost ratios than PFSUM and even the conventional online algorithm SUM. This shows that it is important to take advantage of the characteristics of the Bahncard (it is valid for a fixed time period only and provides the same discount to all the tickets purchased therein) when designing learning-augmented algorithms. ( 5) PFSUM consistently outperforms SRL, particularly in scenarios with significant prediction errors. While the performance of SRL improves with increasing λ under high prediction errors, as a larger λ leads to reduced reliance on the predictions and enhances the algorithm's robustness, its overall performance remains inferior to that of SUM. 
discussions and conclusions: 
 We have developed a new learning-augmented algorithm called PFSUM for the Bahncard problem. PFSUM makes predictions on the short-term future only, aligning closely with the temporal nature of the Bahncard problem and the practice of real-world ML predictions. We present a comprehensive analysis of PFSUM's competitive ratio under arbitrary prediction errors by a divide-and-conquer approach. Experimental results demonstrate significant performance advantages of PFSUM.Different from prior works, we do not predict a full sequence of requests from the outset, and predict just a sum of near-future requests (cost) when needed. In some online problems with temporal aspects, compared with individual requests, the aggregated arrival pattern across a group of requests is more predictable (see, e.g., [34] ). Thus, our approach can enhance the learnability of ML predictions. We believe that our analysis and result will be useful to various applications of the Bahncard problem as well as other problems with recurring renting-or-buying phenomena. 
 
 Appendix: Im et al. [26] studied a problem somewhat related to the Bahncard problem, focusing on TCP acknowledgement enhanced with machine-learned predictions. In the TCP acknowledgment problem, a sequence of requests unfolds over time, each requiring acknowledgment, and a single acknowledgment can address all pending requests simultaneously. The objective here is to optimize the combined total of request delay and acknowledgement cost (strike a balance between minimizing the delays in addressing requests and the costs of acknowledgments). Im et al. [26] introduced a novel prediction error measure that estimates how much the optimal objective value changes when the difference between the actual numbers of requests and the predictions varies. Im et al. [26] took into account the temporal aspects of requests, akin to a previous work [9] . The new error measure enables their algorithm to achieve near-optimal consistency and robustness simultaneously. Our investigation into the Bahncard problem differs significantly from theirs in terms of techniques employed. The main differences are summarized as follows.• In [26] , predictions are made for a full sequence of TCP acknowledgment requests. The prediction necessitates a discrete formulation, where time is partitioned into slots of equal length. In contrast, our approach refrains from discretization and requires only short-term predictions within a future interval of length T , i.e., the length of the valid time period of a Bahncard. In our work, a prediction on the short-term future is made only when a travel request arises and there is no valid Bahncard, aligning more closely with real-world ML predictions. • Im et al. [26] designed an error measure that is built on the change of the optimal objective value when the algorithm input varies from min{p t , pt } to max{p t , pt }, where p t is the actual number of requests arising in time slot t and pt is the predicted number. By contrast, our error measure estimates the quality of predictions directly. Harnessing the novel error measure, Im et al. [26] formulated an intricate algorithm, simultaneously ensuring near-optimal consistency and robustness. In contrast, we design a simple and easily implementable algorithm using short-term predictions and demonstrates its significant performance advantages in experimental evaluations.A.2 Consistency of SUM w is at least(3 -β)/(1 + β)As shown in Figure 8 , consider a travel request sequence σ of five requests: (t 1 , ϵ), (t 2 , γϵ), (t 3 , γ -2ϵ), (t 4 , ϵ), and (t 5 , ϵ), wheret 1 < t 2 ≤ t 1 + w < t 4 + w -T < t 1 + T < t 3 < t 4 < t 2 + T < t 3 + w < t 5 ≤ t 4 + w.By the algorithm definition, SUM w purchases two Bahncards at times t 1 and t 4 respectively, while OPT purchases a Bahncard at time t 2 . When ϵ → 0, we haveSUM w (σ) OPT(σ) = 2C + β(γ + 2ϵ) + (γ -2ϵ) C + β(2γ -2ϵ) + 2ϵ → 2C + βγ + γ C + 2βγ = 3 -β 1 + β . time ǫ ǫ t 1 t 2 t 3 t 4 γ -2ǫ γ -ǫ t 5ǫ Figure 8 : An example where the shaded rectangle (resp. bold line) is the valid time of a Bahncard purchased by SUM w (resp. OPT). SUM w purchases a Bahncard at t 1 because t 2 ≤ t 1 + w and ϵ + (γϵ) ≥ γ. SUM w does not purchase a Bahncard at t 3 since t 3 + w < t 5 and SUM r w (σ; (t 3 + w -T, t 3 ]) + ĉ(σ; (t 3 , t 3 + w]) = (γ -2ϵ) + ϵ < γ. SUM w purchases a Bahncard at t 4 because t 3 , t 4 , t 5 ∈ (t 4 + w -T, t 4 + w] and the total ticket cost is γ.For analyzing consistency, we have ĉ(σ; [t, t + T )) ≡ c(σ; [t, t + T )) holds for any regular request (t, p). Given a travel request sequence σ, we denote by µ 1 < • • • < µ m the times when FSUM purchases Bahncards. Then, the timespan can be divided into epochs E j := [µ j , µ j+1 ) for 0 ≤ j ≤ m, where we define µ 0 = 0 and µ m+1 = ∞. Due to perfect predictions, each epoch E j (except E 0 ) starts with an on phase [µ j , µ j + T ) in which the total regular cost is at least γ, followed by an off phase [µ j + T, µ j+1 ). Epoch E 0 has an off phase only. By the definition of FSUM, for any time t in an off phase when a travel request arises, we haveEQUATIONNote that when both FSUM and OPT do not have a valid Bahncard, they pay the same cost. Thus, we focus on only the time intervals in which at least one of FSUM and OPT has a valid Bahncard. We examine the Bahncards purchased by OPT relative to the Bahncards purchased by FSUM. Clearly, OPT purchases at most one Bahncard in any on phase since the length of an on phase is T , and OPT does not purchase any Bahncard in any off phase by (11) and Corollary 3.2. For any epoch E j , if OPT purchases its i-th Bahncard at time τ i ∈ [µ j , µ j + T ), there are two cases to consider.time on off Case I. The Bahncard expires in the following off phase [µ j + T, µ j+1 ). As shown in Figure 9 , for ease of notation, we use s 1 , ..., s 5 to denote the total regular costs in the time intervalsτ i τ i-1 + T µ j µ j + T µ j+1 τ i + T s 1 s 3 s 2 s 4 s 5 t ′[µ j , max{µ j , τ i-1 + T }), [max{µ j , τ i-1 + T }, τ i ), [τ i , µ j + T ), [µ j + T, τ i + T ), and [τ i + T, µ j+1 )respectively. Here τ i-1 is the time when OPT purchases its (i -1)-th Bahncard. If i = 1, we define τ i-1 = -∞. Note that some of the aforesaid intervals can be empty so that the corresponding total regular cost is 0. Since the total regular cost in an on phase is at least γ, we haveEQUATIONBy Lemma 3.1, we have s 3 +s 4 ≥ γ. If no travel request arises during the time interval [µ j +T, τ i +T ), we have s 4 = 0. Otherwise, we denote by t ′ ∈ [µ j + T, τ i + T ) the time when the first travel request arises in this interval. Since t ′ is in an off phase, it follows from (11) andEQUATIONHence, we always haveEQUATIONThe cost ratio in epoch E j is given byEQUATIONCase II. The Bahncard expires in the on phase of the next epoch, i.e., [µ j+1 , µ j+1 + T ).Case II-A. OPT does not purchase any Bahncard in [τ i + T, µ j+1 + T ). As shown in Figure 10 , we use s 1 , ..., s 7 to denote the total regular costs in the time intervalsEQUATION[µ j+1 + T, µ j+2 ), respectively. Again τ i-1 is the time when OPT purchases its (i -1)-th Bahncard.If i = 1, we define τ i-1 = -∞. Since the total regular cost in an on phase is at least γ, we have If no travel request arises during the time interval [µ j + T, µ j+1 ), we have s 4 = 0 ≤ s 6 . Otherwise, we denote by t ′ ∈ [µ j + T, µ j+1 ) the time when the first travel request arises in this interval. It follows from (11) andEQUATIONEQUATION) time s 2 s 1 s 5 on off s 4 off s 3 s 6 s 7 τ i µ j µ j+1 µ j+2 µ j + T µ j+1 + T τ i + T τ i-1 + T on t ′EQUATION)Together with (17), we get s 4 < s 6 . Therefore, we always haveEQUATIONandEQUATIONThe cost ratio in epochs E j and E j+1 is given byEQUATIONIn addition, the cost ratio in epoch E j is given byEQUATIONEQUATIONCase II-B. After time τ i + T , OPT purchases another x Bahncards at times τ i+1 , ..., τ i+x respectively (x ≥ 1) as shown in Figure 11 . For each k = 1, ..., x, the purchasing time τ i+k falls in the on phase [µ j+k , µ j+k + T ), and the expiry time τ i+k + T falls in the next on phase [µ j+k+1 , µ j+k+1 + T ). OPT does not purchase any new Bahncard in [τ i+x + T, µ j+x+1 + T ). Essentially, the pattern in epoch E j of Case II-A repeats x times, followed by the pattern of Case II-A. By (22) , Case II-C. After time τ i +T , OPT purchases another x Bahncards at times τ i+1 , ..., τ i+x respectively (x ≥ 1) as shown in Figure 12 . For each k = 1, ..., x -1, the purchasing time τ i+k falls in the on phase [µ j+k , µ j+k +T ), and the expiry time τ i+k +T falls in the next on phase [µ j+k+1 , µ j+k+1 +T ). The purchasing time τ i+x falls in the on phase [µ j+x , µ j+x +T ), and the expiry time τ i+x +T falls in the following off phase [µ j+x + T, µ j+x+1 ). Essentially, the pattern in epoch E j of Case II-A repeats x times, followed by the pattern of Case I. By (22) , FSUM(σ; E j+k )/OPT(σ; E j+k ) ≤ 2/(1 + β) for each k = 0, ..., x -1. By (15) , FSUM(σ; E j+x )/OPT(σ; E j+x ) ≤ 2/(1 + β). Hence, If OPT does not purchase any Bahncard in the on phase of E j , it must have purchased a Bahncard in the on phase of E j-1 , and the Bahncard expires in the on phase of E j due to Lemma 3.1. Otherwise, purchasing another Bahncard at the beginning of E j can never increase the total cost, because the total regular cost in the on phase of E j is at least γ. Thus, E j-1 and E j must fall into Case II-A or be the last two epochs of Case II-B, which have been analyzed above.EQUATION) time on off off τ i µ j µ j+1 µ j + T µ j+1 + T τ i-1 + T on … on τ i+1 τ i+x + T τ i + T µ j+x+1 µ j+x+1 + T µ j+2EQUATION)τ i+x µ j+x + T on off off τ i µ j µ j+1 µ j + T µ j+1 + T on … on τ i+1 µ j+x time off τ i + T τ i-1 + T τ i+x-1 + T τ i+x + T µ j+2The theorem follows from ( 15), ( 21), ( 23) and (24) .A.4 Proof of Proposition 4.7 A.4.1 Proof for Pattern III Proposition Restated. If OPT purchases x + 2 Bahncards (x ≥ 0) in successive on phases starting from E j , where (i) the first Bahncard has its purchase time τ i falling in the off phase of E j-1 and its expiry time τ i + T falling in the on phase of E j , (ii) for each k = 1, ..., x, the (k + 1)-th Bahncard has its purchase time τ i+k falling in the on phase of E j+k-1 and its expiry time τ i+k + T falling in the on phase of E j+k , and (iii) the (x + 2)-th Bahncard has its purchase time τ i+x+1 falling in the on phase of E j+x and its expiry time τ i+x+1 + T falling in the off phase of E j+x , thenEQUATIONwhere the upper bound is tight (achievable) when x → ∞.Proof. As shown in Figure 13 , we divide [τ i , τ i+x+1 + T ) into 4x + 5 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, 0, 1, 2, ..., 4x + 3, and let s -1 , s 0 , s 1 , s 2 , ..., s 4x+3 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each k = 0, ..., x -1, the (4k + 3)-th time interval, i.e., [µ j+k + T, µ j+k+1 ) (which is an off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT. time on off First, we observe that the cost ratio PFSUM σ; [τ i , τ i+x+1 + T ) /OPT σ; [τ i , τ i+x+1 + T ) is less than 1/β, as shown below.s 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 µ j + T τ i + T … … on s 4x s 4x+1 … … off s 1 s 0 s -1 τ i+1 + T τ i+2 µ j+x τ i+x+1 off s 4x+2 s 4x+3 τ i+x+1 + T τ i+x + T µ j+x + T µ j+1 + T1 β - PFSUM σ; [τ i , τ i+x+1 + T ) OPT σ; [τ i , τ i+x+1 + T ) = (x + 2)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + (s 4x+2 + s 4x+3 ) β • OPT σ; [τ i , τ i+x+1 + T ) + x k=0 s 4k+1 -β (x + 1)C + β x k=0 s 4k + s 4k+1 + s 4k+2 + x k=-1 s 4k+3 β • OPT σ; [τ i , τ i+x+1 + T ) = (x + 2)C + β x k=0 s 4k + x k=0 s 4k+1 + β x k=0 s 4k+2 + β x k=-1 s 4k+3 β • OPT σ; [τ i , τ i+x+1 + T ) - β(x + 1)C + β 2 x k=0 s 4k + s 4k+1 + s 4k+2 + β x k=-1 s 4k+3 β • OPT σ; [τ i , τ i+x+1 + T ) = [(x + 2) -β(x + 1)]C + β(1 -β) x k=0 s 4k + s 4k+2 + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [τ i , τ i+x+1 + T ) > 0. (since 0 ≤ β < 1)Thus, the following inequality always holds:EQUATIONNext, we analyze the upper bound of the cost ratio. There are two cases to consider.Case I. 0 ≤ η ≤ γ. By Corollary 3.2, for each k = -1, 0, ..., x, the T -future-cost at τ i+k+1 is at least γ, i.e.,EQUATIONBy Lemma 4.2, for each k = 0, ..., x, we haveEQUATION)Note that all the travel requests in the (4k + 2)-th (for k = 0, ..., x) and the (4k + 4)-th (for k = -1, ..., x -1) time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [τ i , τ i+x+1 + T ), we should minimize these s 4k+2 's and s 4k+4 's. If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating ( 27) and (28) . Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume thatEQUATIONIt follows from (29) and Lemma 4.4 thatEQUATIONAs a result, we havePFSUM σ; [τ i , τ i+x+1 + T ) OPT σ; [τ i , τ i+x+1 + T ) = (x + 1)C + β x k=0 s 4k + s 4k+1 + s 4k+2 + x k=-1 s 4k+3 (x + 2)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + (s 4x+2 + s 4x+3 ) + x k=0 s 4k+1 = (x + 1)C + (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + (s 4x+2 + s 4x+3 ) (x + 2)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + (s 4x+2 + s 4x+3 ) + x k=0 s 4k+1 + β x k=0 s 4k+1 -(1 -β) x k=0 s 4k + s 4k+2 (x + 2)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + (s 4x+2 + s 4x+3 ) + x k=0 s 4k+1 ≤ (x + 1)C + (x + 2)(2γ + η) + β x k=0 s 4k+1 -(1 -β) x k=0 s 4k + s 4k+2 (x + 2)C + β(x + 2)(2γ + η) + x k=0 s 4k+1(by (26) ) and ( 30))= (x + 1)C + (x + 2)(2γ + η) + x k=0 s 4k+1 -(1 -β) x k=0 s 4k + s 4k+1 + s 4k+2 (x + 2)C + β(x + 2)(2γ + η) + x k=0 s 4k+1 ≤ (x + 1)C + (x + 2)(2γ + η) + x k=0 s 4k+1 -(1 -β)(x + 1)(γ -η) (x + 2)C + β(x + 2)(2γ + η) + x k=0 s 4k+1(by (28) )EQUATIONCase II. η > γ. By Lemma 4.3, for each k = -1, 0, ..., x, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length at most T ) is less than 2γ + η:EQUATION)On the other hand, the total regular cost in any time interval in an on phase is non-negative. As a result, we have (26) ) and ( 32))PFSUM σ; [τ i , τ i+x+1 + T ) OPT σ; [τ i , τ i+x+1 + T ) < (x + 1)C + (x + 2)(2γ + η) (x + 2)C + β(x + 2)(2γ + η) (byEQUATION)The result follows from (31) and (33) .A tight example is given in Figure 14 , where x → ∞. The upper bound is achieved when 0 ≤ η ≤ γ, for each k = -1, ..., x -1, s 4k+3 = γ + 2η, s 4x+3 → 2γ + η; for each k = 0, ..., x, s 4k = γη, s 4k+1 = s 4k+2 = 0, or when η > γ, for each k = -1, ..., x, s 4k+3 = 2γ + η and for each k = 0, ..., x, s 4k = s 4k+1 = s 4k+2 = 0. time on off If OPT purchases x + 1 Bahncards (x ≥ 0) in successive on phases starting from E j , where (i) the first Bahncard has its purchase time τ i falling in the off phase of E j-1 and its expiry time τ i + T falling in the on phase of E j , and (ii) for each k = 1, ..., x, the (k + 1)-th Bahncard has its purchase time τ i+k falling in the on phase of E j+k-1 and its expiry time τ i+k + T falling in the on phase of E j+k , and (iii) OPT does not purchase any new Bahncard in the on phase of E j+x , thens 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 µ j + T τ i + T … … on s 4x s 4x+1 … … off s 1 s 0 s -1 τ i+1 + T τ i+2 µ j+x τ i+x+1 off s 4x+2 s 4x+3 τ i+x+1 + T τ i+x + T µ j+x + T µ j+1 + T γ + 2η γ -η 0 0 γ + 2η γ -η 0 0 γ -η 0 0 2γ + η (0 ≤ η ≤ γ) 2γ + η 2γ + η 2γ + η 0 0 0 0 0 0 0 0 0 (γ > η)EQUATIONwhere the upper bound is tight (achievable) for any x.Proof. As shown in Figure 15 , we divide [τ i , µ j+x + T ) into 4x + 3 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, 0, 1, 2, ..., 4x + 1, and let s -1 , s 0 , s 1 , s 2 , ..., s 4x+1 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each k = 0, ..., x -1, the (4k + 3)-th time interval, i.e., [µ j+k + T, µ j+k+1 ) (which is an off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT.time on off off First, we observe that the cost ratio PFSUM σ; [τ i , µ j+x + T ) /OPT σ; [τ i , µ j+x + T ) is less than 1/β, as shown below.s 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 s 7 µ j + T µ j+1 + T τ i + T … … on s 4x s 4x+1 … … τ i+x + T off s 1 s 0 s -1 τ i+1 + T τ i+2 µ j+x µ j+x + T1 β - PFSUM σ; [τ i , µ j+x + T ) OPT σ; [τ i , µ j+x + T ) = (x + 1)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 β • OPT σ; [τ i , µ j+x + T ) - β (x + 1)C + β x-1 k=0 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) + x-1 k=-1 s 4k+3 β • OPT σ; [τ i , µ j+x + T ) = (x + 1)C + β x k=0 s 4k + x-1 k=0 s 4k+2 + x-1 k=-1 s 4k+3 + x k=0 s 4k+1 β • OPT σ; [τ i , µ j+x + T ) - β(x + 1)C + β 2 x k=0 s 4k + x k=0 s 4k+1 + x-1 k=0 s 4k+2 + β x-1 k=-1 s 4k+3 β • OPT σ; [τ i , µ j+x + T ) = (1 -β)(x + 1)C + β(1 -β) x k=0 s 4k + x-1 k=0 s 4k+2 + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [τ i , µ j+x + T ) > 0. (since 0 ≤ β < 1)Thus, the following inequality always holds:EQUATIONNext, we analyze the upper bound of the cost ratio. There are two cases to consider.Case I. 0 ≤ η ≤ γ. By Corollary 3.2, for each k = -1, 0, ..., x, the T -future-cost at τ i+k+1 is at least γ, i.e.,EQUATIONBy Lemma 4.2, we haveEQUATION)Note that all the travel requests in the (4k + 2)-th (k = 0, ..., x -1) and the (4k + 4)-th (k = -1, ..., x -1) time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [τ i , µ j+x + T ), we should minimize s 4k+2 and s 4k+4 . If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (36) and (37). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume thatEQUATIONIt follows from (38), and Lemma 4.4 thatEQUATION)As a result, we havePFSUM σ; [τ i , µ j+x + T ) OPT σ; [τ i , µ j+x + T ) = (x + 1)C + β x-1 k=0 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) + x-1 k=-1 s 4k+3 (x + 1)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 = (x + 1)C + (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + β x k=0 s 4k+1 (x + 1)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 - (1 -β) x-1 k=0 s 4k + s 4k+2 + s 4x (x + 1)C + β (s -1 + s 0 ) + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 ≤ (x + 1)C + (x + 1)(2γ + η) + β x k=0 s 4k+1 -(1 -β) x-1 k=0 s 4k + s 4k+2 + s 4x (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1(by ( 35) and (39))= (x + 1)(C + 2γ + η) + x k=0 s 4k+1 -(1 -β) x-1 k=0 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1 ≤ (x + 1)C + (x + 1)(2γ + η) + x k=0 s 4k+1 -(1 -β)(x + 1)(γ -η) (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1(by (37))EQUATION)Case II. η > γ. By Lemma 4.3, for each k = -1, 0, ..., x, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length at most T ) is less than 2γ + η: s 4k+3 < 2γ + η.(41) On the other hand, the total regular cost in any time interval in an on phase is non-negative. As a result, we have 35) and ( 41)PFSUM σ; [τ i , µ j+x + T ) OPT σ; [τ i , µ j+x + T ) ≤ (x + 1)C + (x + 1)(2γ + η) (x + 1)C + β(x + 1)(2γ + η) by (EQUATION)The result follows from (40) and (42).A tight example is given in Figure 16 , where x = 0. The upper bound is achieved when 0 ≤ η ≤ γ, s -1 → γ + 2η, s 0 = γη, and s 1 = 0, or when η > γ, s -1 → 2γ + η, and s 0 = s 1 = 0. A.4.3 Proof for Pattern V Proposition Restated. If (i) there is no Bahncard purchased by OPT expiring in the on phase of E j , (ii) OPT purchases x + 1 Bahncards (x ≥ 0) in successive on phases starting from E j , where (a) for each k = 0, ..., x -1, the (k + 1)-th Bahncard has its purchase time τ i+k falling in the on phase of E j+k and its expiry time τ i+k + T falling in the on phase of E j+k+1 , and (b) the (x + 1)-th Bahncard has its purchase time τ i+x falling in the on phase of E j+x and its expiry time τ i+x + T falling in the off phase of E j+x , thenon off time τ i µ j τ i + T µ j + T s -1 s 0 s 1 γ -η 0 → 2γ + η 0 0 (0 ≤ η ≤ γ) (η > γ) γ + 2ηEQUATIONwhere the upper bound is tight (achievable) for any x.Proof. As shown in Figure 17 , we divide [µ j , τ i+x + T ) into 4x + 3 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by 1, 2, ..., 4x + 3, and let s 1 , s 2 , ..., s 4x+3 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each k = 0, ..., x -1, the (4k + 3)-th time interval, i.e., [µ j+k + T, µ j+k+1 ) (which is an off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT.Next, we analyze the upper bound of the cost ratio. There are two cases to consider. First, we observe that the cost ratio PFSUM σ; [µ j , τ i+x + T ) /OPT σ; [µ j , τ i+x + T ) is less than 1/β, as shown below.… … time s 1 on off off s 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 s 7 µ j + T µ j+1 + T τ i + T … … off s 4x s 4x+1 on s 4x+2 s 4x+3 τ i+x τ i+x + T µ j+x µ j+x + T τ i+x-1 + T1 β - PFSUM σ; [µ j , τ i+x + T ) OPT σ; [µ j , τ i+x + T ) = (x + 1)C + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 β • OPT σ; [µ j , τ i+x + T ) - β (x + 1)C + β x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + s 4x+2 + x k=0 s 4k+3 β • OPT σ; [µ j , τ i+x + T ) = (x + 1)C + β x k=0 s 4k+2 + x k=0 s 4k+3 + x-1 k=0 s 4k+4 + x k=0 s 4k+1 β • OPT σ; [µ j , τ i+x + T ) - β(x + 1)C + β 2 x k=0 s 4k+1 + x k=0 s 4k+2 + x-1 k=0 s 4k+4 + β x k=0 s 4k+3 β • OPT σ; [µ j , τ i+x + T ) = (1 -β)(x + 1)C + β(1 -β) x k=0 s 4k+2 + x-1 k=0 s 4k+4 + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [µ j , τ i+x + T ) > 0. (since 0 ≤ β < 1)Thus, the following inequality always holds:EQUATION)Case I. 0 ≤ η ≤ γ. By Corollary 3.2, for each k = 0, ..., x, the T -future-cost at τ i+k is at least γ, i.e., s 4k+2 + s 4k+3 + s 4k+4 ≥ γ for each k = 0, ..., x -1,EQUATIONBy Lemma 4.2, we haveEQUATIONNote that all the travel requests in the (4k + 2)-th (for k = 0, ..., x) and the (4k + 4)-th (for k = 0, ..., x -1) time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [µ j , τ i+x + T ), we should minimize these s 4k+2 's and s 4k+4 's. If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (45) and (46). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that s 4k+2 ≤ γ for each k = 0, ..., x, s 4k+4 ≤ γ for each k = 0, ..., x -1.It follows from (47) and Lemma 4.4 that s 4k+2 + s 4k+3 + s 4k+4 ≤ 2γ + η for each k = 0, ..., x -1,EQUATIONAs a result, we havePFSUM σ; [µ j , τ i+x + T ) OPT σ; [µ j , τ i+x + T ) = (x + 1)C + β x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + s 4x+2 + x k=0 s 4k+3 (x + 1)C + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 = (x + 1)C + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + s 4x+2 + s 4x+3 + β x k=0 s 4k+1 (x + 1)C + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 - (1 -β) x-1 k=0 s 4k+2 + s 4k+4 + s 4x+2 (x + 1)C + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 ≤ (x + 1)C + (x + 1)(2γ + η) + β x k=0 s 4k+1 -(1 -β) x-1 k=0 s 4k+2 + s 4k+4 + s 4x+2 (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1(by ( 44) and (48))EQUATION)Case II. η > γ. By Lemma 4.3, for each k = 0, ..., x, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length at most T ) is less than 2γ + η: s 4k+3 < 2γ + η.(50) On the other hand, the total regular cost in any time interval in an on phase is non-negative. As a result, we have 44) and ( 50)FSUM σ; [µ j , τ i+x + T ) OPT σ; [µ j , τ i+x + T ) < (x + 1)C + (x + 1)(2γ + η) (x + 1)C + β(x + 1)(2γ + η) by (EQUATION)The result follows from ( 49) and (51).A tight example is given in Figure 18 , where x = 0. The upper bound is achieved when 0 ≤ η ≤ γ, s 1 = 0, s 2 = γη, and s 3 → γ + 2η, or when η > γ, s 1 = s 2 = 0, and Proposition Restated. If (i) there is no Bahncard purchased by OPT expiring in the on phase of E j , (ii) OPT purchases x (x ≥ 1) in successive on phases starting from E j , where for each k = 0, ..., x -1, the (k + 1)-th Bahncard has its purchase time τ i+k falling in the on phase of E j+k and its expiry time τ i+k + T falling in the on phase of E j+k+1 , and (iii) OPT does not purchase any new Bahncard in the on phase of E j+x , and (iv) the total regular cost in the on phase of E j+x is at least γ, thens 3 → 2γ + η. time on off τ i µ j µ j + T µ j+1 τ i + T s 1 s 2 s 3 0 γ -η (0 ≤ η ≤ γ) 0 0 → 2γ + η (η > γ) γ + 2ηEQUATION)where the upper bound is tight (achievable) for any x.Proof. As shown in Figure 19 , we divide [µ j , µ j+x + T ) into 4x + 1 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by 1, 2, ..., 4x + 1, and let s 1 , s 2 , ..., s 4x+1 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each k = 0, ..., x -1, the (4k + 3)-th time interval, i.e., [µ j+k + T, µ j+k+1 ) (which is an off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT.time First, we observe that the cost ratio PFSUM σ; [µ j , µ j+x + T ) /OPT σ; [µ j , µ j+x + T ) < 1/β, as shown below:s 1 on off off s 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 s 7 µ j + T µ j+1 + T τ i + T … … off on s 4x s 4x+1 s 4x-1 τ i+x-1 + T µ j+x … … µ j+2 µ j+x-1 + T µ j+x + T1 β - PFSUM σ; [µ j , µ j+x + T ) OPT σ; [µ j , µ j+x + T ) = xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 β • OPT σ; [µ j , µ j+x + T ) - β (x + 1)C + β x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + x-1 k=0 s 4k+3 β • OPT σ; [µ j , µ j+x + T ) = (1 -β)xC -βC + β(1 -β) x-1 k=0 s 4k+2 + β(1 -β) x-1 k=0 s 4k+4 + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [µ j , µ j+x + T ) > (1 -β)xC -βC + β(1 -β) x-1 k=0 s 4k+2 + x-2 k=0 s 4k+4 β • OPT σ; [µ j , µ j+x + T ) + (1 -β 2 ) x-1 k=0 s 4k+1 + β(1 -β)(s 4x + s 4x+1 ) β • OPT σ; [µ j , µ j+x + T ) (since 0 ≤ β < 1) ≥ (1 -β)xC -βC + β(1 -β) x-1 k=0 s 4k+2 + x-2 k=0 s 4k+4 β • OPT σ; [µ j , µ j+x + T ) + (1 -β 2 )x-1k=0 s 4k+1 + -β)γ β • OPT σ; [µ j , µ j+x + T ) (since s 4x + s 4x+1 ≥ γ) = (1 -β)xC + β(1 -β) x-1 k=0 s 4k+2 + x-2 k=0 s 4k+4 + (1 -β 2 ) x-1 k=0 s 4k+1 β • OPT σ; [µ j , µ j+x + T ) > 0.(53)Thus, the following inequality always holds:EQUATION)There are two cases to consider.Case I. 0 ≤ η ≤ γ. By Corollary 3.2, for each k = 0, ..., x -1, the T -future-cost at τ i+k is at least γ, i.e.,EQUATION)On the other hand, by Lemma 4.2 and the (iv)-th condition of the proposition, we haveEQUATION)Note that for each k = 0, ..., x -1, all the travel requests in the (4k + 2)-th and the (4k + 4)-th time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [µ j , µ j+x + T ), we should minimize s 4k+2 and s 4k+4 . If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (55) and (56) (except for s 4x ). For s 4x , if it is greater than γ, the cost ratio can be increased by decreasing it to γ without violating (55) and (56). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume thatEQUATIONIt follows from (57) and Lemma 4.4 that, for each k = 0, ..., x -2,EQUATION)For k = x -1, we still haveEQUATION)Otherwise, there must exist a time t in the off phase of E j+x-1 such that PFSUM purchases a Bahncard, leading to a contradiction.As a result,PFSUM σ; [µ j , µ j+x + T ) OPT σ; [µ j , µ j+x + T ) = (x + 1)C + β x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + x-1 k=0 s 4k+3 xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 = (x + 1)C + β x k=0 s x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 -(1 -β) x-1 k=0 s 4k+2 + s 4k+4 xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 = (x + 1)C + x k=0 s 4k+1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 xC + β x-1 k=0 s 4k+2 + s 4k+3 s 4k+4 + x k=0 s 4k+1 - (1 -β) x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 = (x + 1)C + x k=0 s 4k+1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 - (1 -β) (s 1 + s 2 ) + x-1 k=1 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 ≤ (x + 1)C + x k=0 s 4k+1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 -(1 -β) x(γ -η) + γ] xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1(by (56)) 54), (58), and (59))≤ (x + 1)C + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 -(1 -β) x(γ -η) + γ] xC + β x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 (since x k=0 s 4k+1 ≥ 0) ≤ (x + 1)C + x(2γ + η) -(1 -β) x(γ -η) + γ] xC + βx(2γ + η) (by (EQUATION)Case II. η > γ. In this case, the total regular cost in any time interval in an on phase can be zero (except for the on phase of E j+x ):EQUATIONOn the other hand, by Lemma 4.3, for each k = 0, ..., x -2, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length at most T ) is less than 2γ + η:s 4k+3 < 2γ + η. (62) For k = x -1, we have s 4x-1 < γ + η.(63) Otherwise, there must exist a time t in the off phase of E j+x-1 such that PFSUM purchases a Bahncard, leading to a contradiction.PFSUM σ; [µ j , µ j+x + T ) OPT σ; [µ j , µ j+x + T ) < (x + 1)C + (x -1)(2γ + η) + (γ + η) + βγ xC + βx(2γ + η)(by ( 61), (62), and (63))EQUATION)The result follows from ( 60) and (64).A tight example for Proposition 4.8 is given in Figure 20 , where x = 1. The upper bound is achieved when 0 ≤ η ≤ γ, s 1 = s 5 = 0, s 2 = γ -η, s 3 → 2η, and s 4 = γ, or when η > γ, s 1 = s 2 = s 5 = 0, s 3 → γ + η, and s 4 = γ. which expires in the same off phase, (ii) there is no Bahncard purchased by OPT expiring in the on phase of E j (j > l), (iii) OPT x Bahncards (x ≥ 1) in successive on phases starting from E j , where for each k = 0, ..., x -1, the (k + 1)-th Bahncard has its purchasing time τ i+k falling in the on phase of E j+k and its expiry time τ i+k + T falling in the on phase of E j+k+1 , and (iv) OPT does not purchase any new Bahncard in the on phase of E j+x , then(η > γ) 0 γ µ j τ i µ j + T µ j+1 τ i + T µ j+1 + T s 1 s 5 γ -η 2η 0 γ + η γ 0 0EQUATIONwhere the upper bound is tight (achievable) for any x.Proof. As shown in Figure 21 , we divide[τ k , τ k + T ) ∪ [µ j , µ j+x + T ) into 4x + 2 time intervals,where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, 1, ..., 4x+1, and let s -1 , s 1 , ..., s 4x+1 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each k = 0, ..., x -1, the (4k + 3)-th time interval, i.e., [µ j+k + T, µ j+k+1 ) (which is an off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT.time First, we observe that the cost ratios 1 on off off s 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 s 7 µ j + T µ j+1 + T τ i + T … … off on s 4x s 4x+1 s 4x-1 τ i+x-1 + T µ j+x … … µ j+2 µ j+x-1 + T µ j+x + T off s -1 VI II … … … … τ k τ k + TPFSUM σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) /OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) is less than 1/β, as shown below: 1 β - PFSUM σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) = (x + 1)C + β s -1 + x-1 k=0 (s 4k+2 + s 4k+3 + s 4k+4 ) + x k=0 s 4k+1 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) - β (x + 1)C + β x-1 k=0 (s 4k+1 + s 4k+2 + s 4k+4 ) + s 4x+1 + s -1 + x-1 k=0 s 4k+3 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) = (1 -β)(x + 1)C + β(1 -β) x-1 k=0 (s 4k+2 + s 4k+4 ) + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) > 0. (since 0 ≤ β < 1)Thus, the following inequality always holds:EQUATIONNext, we analyze the upper bound of the cost ratio. Note that by Lemma 4.3, we haveEQUATIONThere are two cases to consider.Case I. 0 ≤ η ≤ γ. By Corollary 3.2, for each k = 0, ..., x -1, the T -future-cost at τ i+k is at least γ, i.e.,EQUATIONBy Lemma 4.2, we haveEQUATIONNote that for each k = 0, ..., x -1, all the travel requests in the (4k + 2)-th and the (4k + 4)-th time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in[τ k , τ k + T ) ∪ [µ j , µ j+x + T ), we should minimize s 4k+2 and s 4k+4 . If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (68) and (69). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume thatEQUATIONEQUATIONIt follows from (70), (71) and Lemma 4.4 that, for each k = 0, ..., x -1,EQUATIONAs a result, we havePFSUM σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) = (x + 1)C + β x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + s -1 + x-1 k=0 s 4k+3 (x + 1)C + β s -1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 < (x + 1)C + (2γ + η) + β x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + x-1 k=0 s 4k+3 (x + 1)C + β 2γ + η + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1(by (67))= (x + 1)C + (2γ + η) + β x k=0 s 4k+1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 -(1 -β) x-1 k=0 s 4k+2 + s 4k+4 (x + 1)C + β 2γ + η + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 ≤ (x + 1)C + β x k=0 s 4k+1 + (x + 1)(2γ + η) -(1 -β) x-1 k=0 s 4k+2 + s 4k+4 (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1(by (66) and (72))EQUATION)Case II. η > γ. By Lemma 4.3, for each k = 0, ..., x -1, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length at most T ) is less than 2γ + η:EQUATIONOn the other hand, the total regular cost in any time interval in an on phase is non-negative. As a result, we haveEQUATIONEQUATIONThe result follows from ( 73) and (75).A.6.2 Non-Augmented Pattern VI Combined with Pattern III Proposition Restated. If OPT purchases x + 2 Bahncards (x ≥ 0) starting from the off phase of E l-1 , where (i) the first Bahncard has its purchase time τ k falling in the off phase of E l-1 and its expiry time τ k + T falling in the on phase of E l , (ii) for each p = 1, ..., x, the (p + 1)-th Bahncard has its purchase time τ k+p falling in the on phase of E l+p-1 and its expiry time τ k+p + T falling in the on phase of E l+p , (iii) the (x + 2)-th Bahncard has its purchase time τ k+x+1 falling in the on phase of E l+x and its expiry time τ k+x+1 + T falling in the off phase of E l+x , and for some j ≥ l and i ≥ k, OPT purchases y Bahncards (y ≥ 0) in successive on phases starting from E j+x+1 , where for each p = 0, ..., y -1, the (p + 1)-th Bahncard has its purchasing time τ i+x+p+2 falling in the on phase of E j+x+p+1 and its expiry time τ i+x+p+2 + T falling in the on phase of E j+x+p+2 , and (v) OPT does not purchase any new Bahncard in the on phase of E j+x+y+1 , thenEQUATION)Proof. As shown in Figure 22 , we divide [τ k , τ k+x+1 +T )∪[µ j+x+1 , µ j+x+y+1 +T ) into 4(x+y)+6 time intervals, where each time intervals starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. The first 4x + 5 time intervals, from time τ i to τ i+x+1 + T , are concerned time duration of Pattern III. The total regular costs in these intervals are denoted by s -1 , s 0 , s 1 , ..., s 4x+3 , respectively. [µ j+x+1 , µ j+x+y+1 + T ) is the concerned interval of Pattern VI, which is divided into 4y + 1 time intervals. The total regular costs in these intervals are denoted by q 1 , ..., q 4y+1 , respectively.For ease of notation, we introduce θ k := s 4k+2 + s 4k+3 + s 4k+4 , and δ k := q 4k+2 + q 4k+3 + q 4k+4 . First, we observe that the cost ratio PFSUM σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) /OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) is less than 1/β,µ j+x+1 µ j+x+2 µ j+x+y+1 τ i+x+2 τ i+x+3 τ i+x+y+1 s -1 s 4x+3 q 1 q 4y+1 III VI … … … … τ k µ l τ k+1 µ l+1 τ k+2 µ l+x τ k+x+11 β - PFSUM σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) = (x + 2)C + β s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) + x k=0 s 4k+1 + s 4x+4 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) -β • (x + 1)C + β x k=0 s 4k + s 4k+1 + s 4k+2 + x k=-1 s 4k+3 + s 4x+4 β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) -β • (y + 1)C + β y-1 k=0 q 4k+1 + q 4k+2 + q 4k+4 + q 4y+1 + y-1 k=0 q 4k+3 β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) = (1 -β)(x + y + 2)C + β(1 -β)( x k=0 s 4k+2 + x k=0 s 4k ) + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) + β(1 -β)( y-1 k=0 q 4k+2 + y-1 k=0 q 4k+4 ) + (1 -β 2 ) y k=0 q 4k+1 β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) > (1 -β)(x + y + 2)C β • OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) (since 0 ≤ β < 1, C > 0) > 0.Thus, the following inequality always holds:EQUATIONEQUATIONBy Lemma 4.2, we have      s 4k + s 4k+1 + s 4k+2 ≥ γη for each k = 0, 1, ..., x. q 1 + q 2 ≥ γη q 4y + q 4y+1 ≥ γη q 4k + q 4k+1 + q 4k+2 ≥ γη for each k = 1, 2, ..., y -1.(79)Note that for Pattern III, all the travel requests in the (4k + 2)-th (for k = 0, ..., x) and the (4k + 4)-th (for k = -1, ..., x -1) time intervals are reduced requests of both PFSUM and OPT, similar for Pattern VI. Thus, to maximize the cost ratio in [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ), we should minimize these s 4k+2 's, s 4k+4 's, q 4k+2 's, and q 4k+4 's. If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (78) and (79). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume that      s 4k+2 ≤ γ for each k = 0, ..., x, s 4k+4 ≤ γ for each k = -1, ..., x -1, q 4k+2 ≤ γ for each k = 0, ..., y -1, q 4k+4 ≤ γ for each k = 0, ..., y -1.(80)It follows from (80) and Lemma 4.4 that,EQUATIONAs a result, we have 77) and ( 81))PFSUM σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) = (x + 1)C + s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k + x k=0 s 4k+1 -(1 -β) x k=0 (s 4k + s 4k+1 + s 4k+2 ) (x + 2)C + β s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k + x k=0 s 4k+1 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 + (y + 1)C + y k=0 q 4k+1 + y-1 k=0 δ k -(1 -β) q 1 + q 2 + q 4y + q 4y+1 + y-1 k=1 (q 4k + q 4k+1 q 4k+2 ) (x + 2)C + β s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k + x k=0 s 4k+1 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 ≤ (x + 1)(1 -β)η + s -1 + s 0 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 + x-1 k=0 θ k (x + 2)C + β s -1 + s 0 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 + x-1 k=0 θ k + yC + β y-1 k=0 δ k + y k=0 q 4k+1 + (y + 1)(1 -β)η + y-1 k=0 δ k + y k=0 q 4k+1 (x + 2)C + β s -1 + s 0 + s 4x+2 + s 4x+3 + x k=0 s 4k+1 + x-1 k=0 θ k + yC + β y-1 k=0 δ k + y k=0 q 4k+1 (by (79)) ≤ (x + 1)(1 -β)η + s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k + (y + 1)(1 -β)η + y-1 k=0 δ k (x + 2)C + β(s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k ) + yC + β y-1 k=0 δ k (since x k=0 s 4k+1 ≥ 0, y k=0 q 4k+1 ≥ 0) = (x + y + 2)(1 -β)η + (s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k ) + y-1 k=0 δ k (x + y + 2)C + β s -1 + s 0 + s 4x+2 + s 4x+3 + x-1 k=0 θ k + βy y-1 k=0 δ k ≤ (x + y + 2)(1 -β)η + (x + y + 2)(2γ + η) (x + y + 2)C + β(x + y + 2)(2γ + η) (by (EQUATIONCase II. η > γ. By Lemma 4.3, for Pattern III, the total regular cost in the (4k + 3)-th (for k = -1, ..., x) time interval (which is in an off phase and has length at most T ) is less than 2γ + η, similar for Pattern VI. Thus we have s 4k+3 < 2γ + η for each k = -1, ..., x, q 4k+3 < 2γ + η for each k = 0, 1, ..., y -1.On the other hand, the total regular cost in any time interval in an on phase is non-negative, so it can be minimized to zero. As a result, we have 77) and (83))PFSUM σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) OPT σ; [τ k , τ k+x+1 + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) ≤ (x + 1)C + x k=-1 s 4k+3 + (y + 1)C + y-1 k=0 q 4k+3 (x + 2)C + β s -1 + s 4x+3 + x-1 k=0 s 4k+3 + yC + β y-1 k=0 q 4k+3 < (x + 1)C + (x + 2)(2γ + η) + (y + 1)C + y(2γ + η) (x + 2)C + β(x + 2)(2γ + η) + yC + βy(2γ + η) (by (EQUATIONThe result follows from ( 82) and (84). , τ k = µ l , (ii) there is no Bahncard purchased by OPT expiring in the on phase of E j (l < j), (iii) OPT purchases x Bahncards (x ≥ 1) in successive on phases starting from E j , where for each k = 0, ..., x -1, the (k + 1)-th Bahncard has its purchasing time τ i+k falling in the on phase of E j+k and its expiry time τ i+k + T falling in the on phase of E j+k+1 , and (iv) OPT does not purchase any new Bahncard in the on phase of E j+x , thenEQUATIONwhere the upper bound is irrelevant with x.Proof. As shown in Figure 23 , we divide [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) into 4x + 2 time intervals, where each time interval starts and ends with the time when OPT or PFSUM purchases a Bahncard or a Bahncard purchased by OPT or PFSUM expires. Let these intervals be indexed by -1, 1, ..., 4x+1, and let s -1 , s 1 , ..., s 4x+1 denote the total regular costs in these intervals respectively. By definition, it is easy to see that for each k = 0, ..., x -1, the (4k + 3)-th time interval, i.e., [µ j+k + T, µ j+k+1 ) (which is an off phase), is shorter than T since it is within the valid time of a Bahncard purchased by OPT.time First, we observe that the cost ratio PFSUM σ;s 1 on off off s 3 τ i µ j µ j+1 on s 2 s 4 s 5 τ i+1 s 6 s 7 µ j + T µ j+1 + T τ i + T … … off on s 4x s 4x+1 s 4x-1 τ i+x-1 + T µ j+x … … µ j+2 µ j+x-1 + T µ j+x + T s -1 VI I on … … … … τ k (µ l ) τ k + T off[τ k , τ k + T ) ∪ [µ j , µ j+x + T ) /OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T) is less than 1/β, as shown below:1 β - PFSUM σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) = (x + 1)C + β s -1 + x-1 k=0 (s 4k+2 + s 4k+3 + s 4k+4 ) + x k=0 s 4k+1 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) - β (x + 2)C + β s -1 + x-1 k=0 (s 4k+1 + s 4k+2 + s 4k+4 ) + s 4x+1 + x-1 k=0 s 4k+3 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) = (1 -β)(x + 1)C -βC + β(1 -β) s -1 + x-1 k=0 (s 4k+2 + s 4k+4 ) + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) ≥ (1 -β)(x + 1)C + β(1 -β) x-1 k=0 (s 4k+2 + s 4k+4 ) + (1 -β 2 ) x k=0 s 4k+1 β • OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) (since s -1 ≥ γ) > 0. (since 0 ≤ β < 1)Thus, the following inequality always holds:EQUATION)There are two cases to consider.Case I. 0 ≤ η ≤ γ. By Corollary 3.2, for each k = 0, ..., x -1, the T -future-cost at τ i+k is at least γ, i.e.,EQUATIONBy Lemma 4.2, we haveEQUATIONNote that for each k = 0, ..., x -1, all the travel requests in the (4k + 2)-th and the (4k + 4)-th time intervals are reduced requests of both PFSUM and OPT. Thus, to maximize the cost ratio in [τ k , τ k + T ) ∪ [µ j , µ j+x + T ), we should minimize s 4k+2 and s 4k+4 . If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (87) and (88). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume thatEQUATION)It follows from ( 89), (90) and Lemma 4.4 that, for each k = 0, ..., x -1,EQUATION)As a result, we havePFSUM σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) = (x + 2)C + β s -1 + x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + x-1 k=0 s 4k+3 (x + 1)C + β s -1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 ≤ (x + 2)C + β γ + x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 + x-1 k=0 s 4k+3 (x + 1)C + β γ + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 (by (88)) = (x + 2)C + βγ + β x k=0 s 4k+1 + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 -(1 -β) x-1 k=0 s 4k+2 + s 4k+4 (x + 1)C + β γ + x-1 k=0 s 4k+2 + s 4k+3 + s 4k+4 + x k=0 s 4k+1 ≤ (x + 2)C + βγ + β x k=0 s 4k+1 + x(2γ + η) -(1 -β) x-1 k=0 s 4k+2 + s 4k+4 (x + 1)C + β(γ + x(2γ + η)) + x k=0 s 4k+1(by ( 86) and (91))= (x + 2)C + βγ + x k=0 s 4k+1 + x(2γ + η) -(1 -β) x-1 k=0 s 4k+1 + s 4k+2 + s 4k+4 + s 4x+1 (x + 1)C + β(γ + x(2γ + η)) + x k=0 s 4k+1 = (x + 2)C + βγ + x k=0 s 4k+1 + x(2γ + η) (x + 1)C + β(γ + x(2γ + η)) + x k=0 s 4k+1 - (1 -β) (s 1 + s 2 ) + x-1 k=1 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) (x + 1)C + β(γ + x(2γ + η)) + x k=0 s 4k+1 ≤ (x + 2)C + βγ + x k=0 s 4k+1 + x(2γ + η) -(1 -β)(x + 1)(γ -η) (x + 1)C + β(γ + x(2γ + η)) + x k=0 s 4k+1(by (88))EQUATIONCase II. η > γ. By Lemma 4.3, for each k = 0, ..., x -1, the total regular cost in the (4k + 3)-th time interval (which is in an off phase and has length at most T ) is less than 2γ + η:EQUATIONOn the other hand, the total regular cost in any time interval in an on phase is non-negative, except for s -1 , which is at least γ:EQUATION)As a result, we havePFSUM σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) OPT σ; [τ k , τ k + T ) ∪ [µ j , µ j+x + T ) < (x + 2)C + βγ + x(2γ + η) (x + 1)C + β(γ + x(2γ + η))(by ( 86), (93), and (94))EQUATIONThe result follows from (92) and (95). , where (i) the first Bahncard has its purchase time τ k falling in the off phase of E l-1 and its expiry time τ k + T falling in the on phase of E l , (ii) for each p = 1, ..., x, the (p + 1)-th Bahncard has its purchase time τ k+p falling in the on phase of E l+p-1 and its expiry time τ k+p + T falling in the on phase of E l+p , and for some j ≥ l and i ≥ k, OPT purchases y Bahncards (y ≥ 0) in successive on phases starting from E j+x+1 , where for each p = 0, ..., y -1, the (p + 1)-th Bahncard has its purchasing time τ i+x+p+1 falling in the on phase of E j+x+p+1 and its expiry time τ i+x+p+1 + T falling in the on phase of E j+x+p+2 , and (v) OPT does not purchase any new Bahncard in the on phase of E j+x+y+1 , thenEQUATIONwhere the upper bound is tight (achievable) for any x.Proof. As shown in Figure 24 According to Proposition 4.10. In IV of ( 9), the total cost of travel requests in the last on phase of Pattern IV and the following off phase is at least γ. Thus we haveµ j+x+1 µ j+x+2 µ j+x+y+1 τ i+x+2 s -1 q 1 q 4y+1 s 4x+1 IV VI τ i+x+1 τ i+x+y τ k µ l τ k+1 µ l+1 τ k+2 µ l+x … … … … off s 4x+2 µ l+x+1EQUATIONFirst, we observe that the cost ratio PFSUM σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) /OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) is less than 1/β, as shown below:1 β - PFSUM σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) = (x + 1)C + β s -1 + s 0 + x-1 k=0 (s 4k+2 + s 4k+3 + s 4k+4 ) + x k=0 s 4k+1 + s 4x+2 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) + yC + β y-1 k=0 (q 4k+2 + q 4k+3 + q 4k+4 ) + y k=0 q 4k+1 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) -β • (x + 1)C + β x-1 k=0 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) + x-1 k=-1 s 4k+3 + s 4x+2 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) -β • (y + 1)C + β y-1 k=0 q 4k+1 + q 4k+2 + q 4k+4 + q 4y+1 + y-1 k=0 q 4k+3 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) = (x + 1)(1 -β)C + β(1 -β)( x-1 k=0 s 4k+2 + x k=0 s 4k ) + (1 -β 2 ) x k=0 s 4k+1 + (1 -β)s 4x+2 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) + y -β(y + 1) C + β(1 -β) y-1 k=0 ( y-1 k=0 (q 4k+2 + q 4k+4 ) + (1 -β 2 ) y k=0 q 4k+1 + (1 -β)s 4x+2 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) ≥ (x + y)(1 -β) + (1 -2β) C + β(1 -β)s 4x + (1 -β 2 )s 4x+1 + (1 -β)s 4x+2 β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) ≥ (x + y)(1 -β) + (1 -2β) C + β(1 -β)(s 4x + s 4x+1 + s 4x+2 ) β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) (since 0 ≤ β < 1) ≥ (x + y)(1 -β) + (1 -2β) C + β(1 -β)γ β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) (by (97)) = (x + y)(1 -β) + (1 -β) C β • OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) > 0. (since 0 ≤ β < 1, C > 0)Thus, the following inequality always holds:EQUATIONCase I. 0 ≤ η ≤ γ. By Corollary 3.2, the T -future-cost at τ i+k+1 is at least γ, i.e.,EQUATIONBy Lemma 4.2, we haveEQUATIONNote that for Pattern IV, all the travel requests in the (4k+2)-th and the (4k+4)-th (for k = 0, ..., x-1) time intervals are reduced requests of both PFSUM and OPT, similar for Pattern VI. Thus, to maximize the cost ratio in [τ k , µ l+x + T ) ∪ [µ j+x+1 , µ j+x+y+1 + T ), we should minimize these s 4k+2 's and s 4k+4 's. If they are greater than γ, the cost ratio can be increased by decreasing s 4k+2 or s 4k+4 to γ without violating (99) and (100). Thus, for the purpose of deriving an upper bound on the cost ratio, we can assume thatEQUATIONIt follows from (101) and Lemma 4.4 that, s -1 + s 0 ≤ 2γ + η s 4k+2 + s 4k+3 + s 4k+4 ≤ 2γ + η for each k = 0, ..., x -1, q 4k+2 + q 4k+3 + q 4k+4 ≤ 2γ + η for each k = 0, ..., y -1As a result, we have 98) and (102))PFSUM σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) OPT σ; [τ k , µ l+x+1 ) ∪ [µ j+x+1 , µ j+x+y+1 + T ) = (x + 1)C + (s -1 + s 0 ) + x-1 k=0 θ k + β x k=0 s 4k+1 + s 4x+2 -(1 -β) x-1 k=0 s 4k + s 4k+2 + s 4x (x + 1)C + β(s -1 + s 0 + x-1 k=0 θ k ) + x k=0 s 4k+1 + s 4x+2 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 + (y + 1)C + y k=0 q 4k+1 + y-1 k=0 δ k -(1 -β) y-1 k=0 q 4k+1 + q 4k+2 + q 4k+4 + q 4y+1 (x + 1)C + β(s -1 + s 0 + x-1 k=0 θ k ) + x k=0 s 4k+1 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 ≤ (x + 1)C + (s -1 + s 0 ) + x-1 k=0 θ k + β x k=0 s 4k+1 -(1 -β) x-1 k=0 s 4k + s 4k+2 + s 4x (x + 1)C + β(s -1 + s 0 + x-1 k=0 θ k ) + x k=0 s 4k+1 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 + (y + 1)C + y k=0 q 4k+1 + y-1 k=0 δ k -(1 -β) y-1 k=0 q 4k+1 + q 4k+2 + q 4k+4 + q 4y+1 (x + 1)C + β(s -1 + s 0 + x-1 k=0 θ k ) + x k=0 s 4k+1 + yC + β y-1 k=0 δ k + y k=0 q 4k+1 (since s 4x+2 ≥ 0) ≤ (x + 1)C + (x + 1)(2γ + η) + x k=0 s 4k+1 -(1 -β) x-1 k=0 s 4k + s 4k+1 + s 4k+2 + (s 4x + s 4x+1 ) (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1 + yC + βy(2γ + η) + y k=0 q 4k+1 + (y + 1)C + y k=0 q 4k+1 + y(2γ + η) -(1 -β) q 1 + q 2 + y-1 k=1 q 4k + q 4k+1 + q 4k+2 + q 4y + q 4y+1 (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1 + yC + βy(2γ + η) + y k=0 q 4k+1 (by (≤ (x + 1)C + (x + 1)(2γ + η) + x k=0 s 4k+1 -(1 -β) x(γ -η) + γ (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1 + yC + βy(2γ + η) + y k=0 q 4k+1 + (y + 1)C + y k=0 q 4k+1 + y(2γ + η) -(1 -β)(y + 1)(γ -η) (x + 1)C + β(x + 1)(2γ + η) + x k=0 s 4k+1 + yC + βy(2γ + η) + y k=0 q 4k+1(by (97) and (100))EQUATION)Case II. η > γ. By Lemma 4.3, for Pattern IV, the total regular cost in the (4k + 3)-th (for k = -1, ..., x) time interval (which is in an off phase and has length at most T ) is less than 2γ + η, similar for Pattern VI. Thus we haveEQUATIONOn the other hand, the total regular cost in any time interval in an on phase is non-negative, so it can be minimized to zero, except the last on phase of Pattern IV. As a result, we have (105)EQUATIONThe result follows from (103), and (105).For commuters, Figures 25 to 30 demonstrate the performance of various algorithms under different settings of β, C, and T . Additionally, with the practical significance of these parameters in mind, we increase C or decrease T when β is reduced. In Figure 26 , where C is exceptionally high, PFSUM, SUM w , and SUM all tend towards not purchasing Bahncards. However, in this scenario, FSUM's competitive ratio escalates due to its complete reliance on predictions with large errors.Additional results for occasional travelers are presented in Figures 28 to 30. These figures exhibit a consistent pattern, with PFSUM demonstrating its consistency in scenarios of small prediction error. Furthermore, PFSUM proves its robustness in cases of extremely large prediction errors, particularly evident in Figure 30 . Here, while all other prediction-incorporated algorithms have competitive ratios of approximately 1.2 or higher, PFSUM consistently maintains a competitive ratio of less than 1.1. Justification: The abstract and introduction clearly state the contributions made, matching both theoretical and experimental results.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Wang et al. [20] studied a restricted setting where time is slotted into hours and purchases are performed only at the beginning of slots because virtual machine instances in clouds are billed in an hourly manner. 


Decision: The paper presents a novel, well-explained method with strong theoretical backing and empirical validation, offering significant improvements over previous work. The algorithms and ideas are presented clearly and intuitively, and the paper is well-written overall.  A key strength is that the algorithm simplifies decision-making by not requiring prediction of the entire future input.    

Some reviewers deemed the experimental validation insufficient, relying on too few benchmarks. Additionally, the unbounded robustness of the PFSUM algorithm when β approaches 0 and the lack of analysis on the impact of T were highlighted as weaknesses.

Overall, we recommend acceptance as a poster.

To authors: please make sure to address the remaining concerns in the final version.

Reviews: review: paper_summary: paper_summary: In this paper, the authors provide a learning-augmented approach for solving the Bahncard problem, which is a generalization of the ski-rental problem. The authors provide theoretical guarantees for the consistency and robustness of the proposed algorithm PFSUM, which measures the performance of the proposed method compared to an optimal offline method for different levels of prediction error in learning augmentation. The paper also provides empirical results of the proposed method and a comparison with existing methods, which validate the proposed method.
strength_weakness: strength_weakness: * There seems to be a gap between the theoretical result for robustness and the empirical results in the paper. Specifically, when $\beta$ is very small (i.e. when the discount is larger), the bound for competitive ratio tends to be very large. However, the empirical results show that the cost ratio is close to 1 ( as shown in Figure 29, for example). Is there an intuitive reason for this gap?
questions: questions: Please see the Weaknesses.
limitations: limitations: N/A
paper_summary: paper_summary: In this paper, the authors investigate the Bahncard problem in the learning-augmented context. The Bahncard problem is a generalization of ski rental, originating from the railway pass of the German railway company of the same name, where an algorithm must choose between a cheap short-term solution (purchaing railway fare at full price) or an expensive long-term solution (purchasing a Bahncard to receive a discount on all future fares for a set period). Previous works have studied the Bahncard problem extensively in the non-learning-augmented setting, and in the learning-augmented setting by formulating the Bahncard problem as a linear program and applying the primal-dual framework for approximately solving LPs. The authors contribute by proposing an algorithm using the problem structure of the Bahncard problem, independent of the primal-dual framework, that can handle fractional and non-uniform inputs, and utilizes short-term predictions as opposed to an advice on the entire sequence of travels.

Formally, the authors consider problem instances where a series of travel requests arrive at time $t_i$ with ticket price $p_i$. An algorithm can either choose to buy the ticket in full price, or purchase a Bahncard with price $C$, that is valid for a time period of length $T$, and discounts all purchase while valid by a multiplicative factor of $0 \leq \beta \leq 1$. The author's proposed algorithm, PFSUM, is $2/(1+\beta)$-consistent (the competitive ratio when the prediction is accurate) and $1/\beta$-robust (the competitive ratio upper bound with arbitrarily inaccurate prediction).

PFSUM is a very intuitively simple algorithm, that builds upon previous ideas. On a high level, the algorithm examines both the requests that arrived in the past $T$ time period, as well as the predicted requests that will arrive in the next $T$ time period. If the total cost of both the past and the future time period is larger than a certain parameter, the algorithm purchases a Bahncard. The proof strategy divides the algorithm's execution into phases, and bounds the ratio between PFSUM's solution cost and the optimal solution cost for each phase, depending on how the Bahncard purchases overlap between the two solutions.
strength_weakness: strength_weakness: I do not have much major complaints about the paper. One particular issue is that I am not certain how the conclusion of Proposition 4.6 on page 6 is trivial: while I agree the numerator is upper bounded by Lemma 4.3, I do not see an obvious lower bound on the cost of the optimal solution in the denominator, for which Lemma 4.3 only implies an upper bound. A quick delve into the appendices seems to provide traces of arguments supporting $OPT(*) \geq (1+\beta) \gamma + \beta \eta$, so I am inclined to trust the soundness of the author's claims, but I believe that this is important enough an argument to be made explicit in the main corpus.

I am recommending a weak accept as an initial score, but can be convinced by clarifications from the authors to raise the score to accept.
questions: questions: As stated above, I would like to understand the logic behind Proposition 4.6 in more detail, which I believe is important yet non-trivial enough to be explicitly shown in the main corpus.

A few minor questions/suggestions/comments:
- Line 169-172, Section 4.3: The argument behind SUM's success might be more suitable in an earlier section, to help the readers understand both Section 4.1 and 4.2 better.
- Line 188: The definition of the prediction error only concerns the sum of the cost of requests. Is it possible to obtain better bounds and results using a more "fine-grained" error function? This might be an interesting future direction if feasible.
- Line 203, Lemma 4.4: The statement and the figure together slightly confuses me - what if the time interval $[t, t+T)$ does not intersect on phases on both sides? Intuitively the same result should hold with $s_2 = s_4 = 0$, but it is not made explicit by either the lemma statement or the figure.
- Line 221-222, text of Figure 2: "...$x$ can be any non-negative **integers**." It should be **integer**?
- Line 252, Proposition 4.8: The definitions seem to suggest that there should be no regular requests during an on phase, so what is the logic behind the proposition statement? Are the regular cost and the on phase referencing different algorithms?
limitations: limitations: The authors discuss their limitations properly in the introduction and the conclusion sections. No ethical concerns are applicable.
paper_summary: paper_summary: This work studies the Bahncard Problem and proposes a new learning-augmented algorithm, PFSUM. The writing of the paper is clear and easy to follow. The work also provides detailed mathematical proofs for six patterns followed by the experiments validate the theoretical findings.
strength_weakness: strength_weakness: The contributions of this paper are relatively narrow and ambiguous. One significant issue is that the robustness of the PFSUM algorithm remains unbounded when β converges to 0. This limitation undermines the reliability of the algorithm in scenarios where β is very small. Additionally, the parameter T is critical as it defines the boundaries of both the time interval and the prediction interval. However, the paper does not provide a clear analysis of how variations in T impact the competitive ratio, leaving an essential aspect of the algorithm's performance unexplored.

The related work section fails to engage with recent literature that could provide context for this study's contributions. While [12] is a milestone work from 2020, recent publications exploring different facets of the same problem are omitted. These could include the works like "Online algorithms with costly predictions (2023)", "Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem (2024)" and others. Including these works would offer a more comprehensive view of the field's current state. The authors could also indicate the principle and mechanism differences, rather than contextual disparities, between their work and [25]. 

The experimental validation is insufficient, relying on only two benchmarks, which inadequately demonstrates the generalizability and robustness of the proposed algorithm. While the paper claims to measure online algorithm performance using competitive ratios, the experiments primarily employ cost ratios. This discrepancy between theoretical claims and experimental measures undermines the impact of the findings and may lead to misinterpretation of the PFSUM's actual performance improvements.
questions: questions: 1. What are the specific contributions of your work compared to other studies on the same problem, including those not cited in this paper?

2. Have you explored the effects of varying the length of the prediction interval on the performance of PFSUM? Could you provide insights into the trade-off between consistency and robustness in your algorithm?

3. Could you explain why your experimental validation relies on only two benchmarks? What are the reasons behind this choice, and do you believe that including more performance benchmarks could address potential limitations in demonstrating the algorithm's effectiveness?
limitations: limitations: There is no negative societal impact of this work.

Comments: title: (2/2) Official Comment by Authors
(1/2) Official Comment by Authors
My Concerns Remain
Official Comment by Authors
comment: ### **Question 4**

Reference [12] (published in NeurIPS '20) studied several problems, including the Bahncard problem, but experimented only with the TCP acknowledgment problem using three distributions of packet arrivals. *Online Algorithms with Costly Predictions (2023)* was published in AISTATS, but it did not conduct any experimental evaluation. Thus, we disagree that our experimental evaluation is below the expectations of ML/AI conferences. **In fact, to our knowledge, we are the first to conduct extensive experiments for learning-augmented Bahncard algorithms.** Our experimental evaluation covers two types of traveler profiles, each with three types of ticket price distributions, totaling six benchmarks.

Furthermore, it doesn't make sense to evaluate our algorithm with datasets (or benchmarks) for ski rental, since in the Bahncard problem, buying decisions need to be made repeatedly over time, which is the most prominent difference from ski rental and this difference guides the algorithm design. Based on your suggestions, however, we have employed another algorithm for comparison. We adapted Algorithm 2 proposed for ski rental in *Improving Online Algorithms via ML Predictions (NeurIPS '18)* to the Bahncard problem and named it SRL.

Let $\lambda \in (0, 1)$ be a hyperparameter, SRL purchases a Bahncard at a regular travel request $(t,p)$ if and only if there exists a time instant $t' \in [t - T, t]$ that satisfies one of the following conditions:

- The predicted $T$-future-cost at time $t'$ is $\geq \gamma$, and the sum of the costs over the time interval $[t', t]$ is greater than $\lambda \gamma$.
- The predicted $T$-future-cost at time $t'$ is $< \gamma$, and the sum of the costs over $[t', t]$ is $> \frac{\gamma}{\lambda}$.

We found that PFSUM also consistently outperforms SRL in the experiments, as shown below.

- The following table presents the additional results for *Commuters* when $\beta = 0.8$, $T = 10$, $C = 100$, and the price distribution is Pareto.

    | average cost ratio/perturbing probability | 0.0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 |
    |---|---|---|---|---|---|---|---|---|---|---|---|
    | SRL ($\lambda = 1$) | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 | 1.027 |
    | SRL ($\lambda = 0.6$) | 1.025 | 1.036 | 1.042 | 1.045 | 1.046 | 1.047 | 1.047 | 1.048 | 1.048 | 1.048 | 1.048 |
    | SRL ($\lambda = 0.4$) | 1.026 | 1.043 | 1.052 | 1.056 | 1.058 | 1.059 | 1.060 | 1.060 | 1.060 | 1.060 | 1.060 |
    | PFSUM | **1.014** | **1.021** | **1.024** | **1.025** | **1.027** | **1.027** | **1.027** | **1.027** | **1.027** | **1.027** | **1.027** |

- The following table presents the additional results for *Occasional Travelers* when $\beta = 0.8$, $T = 10$, $C = 100$, and the price distribution is Pareto.

    | average cost ratio/perturbing probability | 0.0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1.0 |
    |---|---|---|---|---|---|---|---|---|---|---|---|
    | SRL ($\lambda = 1$)| 1.023 | 1.023 | 1.023 | 1.023 | 1.023 | 1.023 | 1.023 | 1.023 | 1.023 | 1.023 | 1.023 |
    | SRL ($\lambda = 0.6$)| 1.015 | 1.04 | 1.046 | 1.052 | 1.054 | 1.055 | 1.055 | 1.055 | 1.055 | 1.055 | 1.055 |
    | SRL ($\lambda = 0.4$) | 1.013 | 1.07 | 1.088 | 1.104 | 1.110 | 1.114 | 1.115 | 1.115 | 1.115 | 1.115 | 1.115 |
    | PFSUM | **1.010** | **1.017** | **1.022** | **1.022** | **1.010** | **1.017** | **1.022** | **1.022** | **1.010** | **1.017** | **1.022** |

### Concluding Remarks

We are not claiming that our work is perfect. But our work does address learning-augmented Bahncard from perspectives different than existing work (including reference [12] and *Online algorithms with costly predictions (2023)*). We also conduct a comprehensive experimental evaluation to compare with existing algorithms. We believe that our work is valuable to the community and can further stimulate new ideas & studies of the learning-augmented Bahncard problem.
Thank you for your feedback. Below are our responses to your concerns.

### **Question 1**

PFSUM predicts the near future only when it encounters a regular travel request, regardless of how long the time horizon is. However, when the time horizon is sufficiently long, time series predictions (those predicting a long-term future) are **intractable** in the real world (i.e., their prediction complexity is $\infty$). Therefore, it is **inaccurate** to assert that our prediction complexity is much larger.

For practical verification, our experimental evaluation actually includes the type of effectiveness comparison you mentioned, specifically comparing our proposed algorithm, PFSUM, which predicts the near future, with the PDLA algorithm from reference [12], which predicts the long-term future. The results show that **PFSUM consistently and significantly outperforms PDLA**.

Moreover, a once-for-all long-term prediction made at the very beginning struggles to adapt to travel requests whose patterns change dynamically, making it impractical. In contrast, our short-term prediction can overcome this limitation and adapt to such dynamics online.

### **Question 2**

The consistency of PFSUM is **better than** the robustness of other online algorithms even when $\beta = 0$. If $\beta = 0$, the consistency of PFSUM is $\frac{2}{1+\beta} = 2$. For ski-rental, the deterministic algorithm proposed in *Improving Online Algorithms via ML Predictions (NeurIPS '18)* has a robustness of $1 + \frac{1}{\lambda}$ (where $0 < \lambda < 1$ is a hyperparameter), which is greater than 2. For Bahncard, the algorithm proposed in *Online Algorithms with Costly Predictions (2023)* also has a robustness of $1 + \frac{1}{\lambda}$ (where $0 < \lambda < 1$), which is greater than 2.

### **Question 3**

We have derived the competitive ratio as a function of the prediction error. If the prediction error is related to $T$, then the effect of $T$ is implicitly included in our result. In the Bahncard problem, $T$ is a given parameter, not something created in any proposed algorithm that can be tuned. Studying the relation between the prediction error and $T$, if any, is orthogonal to our work.
We are really excited to learn that you have recognized our responses. Thanks for your support for our work!
Thank you for the detailed responses from the authors. I thought through your work and your responses. Although I like your work and enjoy reading the text, a couple of unsolved issues hesitate me to improve my score. 

1) Since your algorithm predicts the near future, the advice complexity could be much larger than those algorithms predicting a long-term future. It will be interesting to explore the cumulative average competitive ratio versus the competitive ratio of a long-term prediction to prove whether the proposed online algorithm is more practical. 

2) Relating the prediction errors to the competitive ratio is interesting but is not new, which can date back to the paper “Improving Online Algorithms via ML Predictions” (2018). The better bounded competitive ratio seems to be more attractive and convincing. Furthermore, if we let β = 0, we can observe that the consistency of PFSUM converges to at least 2. As is known, in the ski rental problem, the worst-case competitive ratio is 2. It means when β = 0, the consistency of PFSUM is worse than the robustness of other online algorithms.

3) If T is related to the prediction errors, will it affect the competitive ratio?

4) As mentioned, you only found one work that conducted experiments on the Bahncard problem, you can still employ other online algorithms on the Bahncard problem, as you do with your reference [12]. A single benchmark cannot show your proposed contributions, particularly in ML/AI conferences. Those works mostly conducted extensive experiments on numerous datasets compared across multiple benchmarks. With the current shape of the paper and your arguments, I just feel this problem as the Achilles’s heel of the work. If the theoretical and experimental results of the Bahncard problem are still limited, you can put your algorithm into a ski rental problem with β = 0 and T converging to infinity. Then, you can have more benchmarks even they may not be the perfect one. This issue makes me wonder whether this venue is the right place for this work. In my opinion, the theoretical computing conferences, e.g., STOC, FOCS, SODA, may be a better fit for this work as they pay more attention on theoretical contributions and will have more audiences to read and cite the work.
Thank you for the clarification. In light of comments from other reviewers and your responses, I am inclined to keep my positive score.
We are very pleased to know that your concerns have been resolved. We also greatly appreciate your high regard for our work's contribution. We will include these discussions in the final paper and try our best to proofread all the details. Once again, we thank you for your constructive suggestions!
Thank you for your response. Yes, please include the proof (sketch) for Proposition 4.6 in the camera-ready version, if accepted. Personally, I am quite excited to see if there is potential in a more 'fine-grained' advice format, but obviously it is out of scope for this submission.

With Proposition 4.6 clarified I am raising my rating from 6 to 7.