Search

The multislope ski-rental problem is an online optimization problem that generalizes the classical ski-rental problem. The player is offered not only a buy and a rent options but also other options that charge both initial and per-time fees. The competitive ratio of the classical ski-rental problem is known to be 2. In contrast, the best known so far on the competitive ratio of the multislope ski-rental problem is an upper bound of 4 and a lower bound of 3.62. In this paper we consider a parametric version of the multislope ski-rental problem, regarding the number of options as a parameter. We prove an upper bound for the parametric problem which is strictly less than 4. Moreover, we give a simple recurrence relation that yields an equation having a lower bound value as its root., Article, IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E103D(3) : 481-488(2020)

The consolidation of the Fog Computing paradigm and the ever-increasing diffusion of Internet of Things (IoT) and smart objects are paving the way toward new integrated solutions to efficiently provide services via short-mid range wireless connectivity. Being the most of the nodes mobile, the node discovery process assumes a crucial role for service seekers and providers, especially in IoT-fog environments where most of the devices run on battery. This paper proposes an original model and a fog-driven architecture for efficient node discovery in IoT environments. Our novel architecture exploits the location awareness provided by the fog paradigm to significantly reduce the power drain of the default baseline IoT discovery process. To this purpose, we propose a deterministic and competitive adaptive strategy to dynamically adjust our energy-saving techniques by deciding when to switch BLE interfaces ON/OFF based on the expected frequency of node approaching. Finally, the paper presents a thorough performance assessment that confirms the applicability of the proposed solution in several different applications scenarios. This evaluation aims also to highlight the impact of the nodes' dynamic arrival on discovery process performance.

We consider a combinatorial variant of the classical ski rental problem --- which we call combinatorial ski rental --- where multiple resources are available to purchase and to rent, and are demanded online. Moreover, the costs of purchasing and renting are potentially combinatorial. The dual problem of combinatorial ski rental, which we call combinatorial online bipartite matching, generalizes the classical online bipartite matching problem into a form where constraints, induced by both offline and online vertices, can be combinatorial. We give a 2-competitive (resp. e / (e - 1)-competitive) deterministic (resp. randomized) algorithm for combinatorial ski rental, and an e / (e - 1)-competitive algorithm for combinatorial online bipartite matching. All these ratios are optimal given simple lower bounds inherited from the respective well-studied special cases. We also prove information-theoretic impossibility of constant-factor algorithms when any part of our assumptions is considerably relaxed.

We consider the following generalization of the classic ski rental problem. A task of unknown duration must be carried out using one of two alternatives called "buy" and "rent", each with a one-time startup cost and an ongoing cost which is a function of the duration. Switching from rent to buy also incurs a one-time cost. The goal is to minimize the competitive ratio, i.e., the worst-case ratio between the cost paid and the optimal cost, over all possible durations. For linear or exponential cost functions, the best deterministic and randomized on-line strategies are well known. In this work we analyze a much more general case, assuming only that the cost functions are continuous and satisfy certain mild monotonicity conditions. For this general case we provide (1) an algorithm that computes the deterministic strategy with the best competitive ratio, and (2) an approximation algorithm that, given e>0$, computes a randomized strategy whose competitive ratio is within (1+e) from the best possible, in time polynomial in e-1. Our algorithm assumes access to a black box that can compute the functions and their inverses, as well as find their extreme points.

We consider the non-additive two-option ski rental problem (NTSR), which includes two options such that each Option i (for i = 1 , 2 ) is characterized by a one-time cost b i and a corresponding rental price a i . Without loss of generality, we assume that a 1 > a 2 ≥ 0 and b 2 > b 1 ≥ 0 . Besides, we have to pay a transition cost c if we switch from Option 1 to Option 2, where c ≥ b 2 − b 1 . We introduce the compound interest rate into the continuous version of NTSR and obtain the optimal deterministic on-line strategy by competitive analysis. Moreover, considering the risk tolerance of decision makers, we present a risk–reward strategy. In addition, we use numerical analysis to analyze the influence of risk tolerance and compound interest rate on the restricted ratio and switching time of the optimal risk–reward strategy. The results demonstrate that the competitive performance is improved when the risk tolerance and compound interest rate are considered.

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options in addition to the pure rent and buy options. For the additive general model, Lotker, Patt-Shamir and Rawitz [in: SIAM J. Discr. Math. 26 (2012) 718–736] obtained a randomized algorithm with the competitive ratio bounded by . However, obtaining a better bound on the competitive factor as a function of the slopes parameters remains an open problem in their paper. In this paper, we study randomized algorithm for the additive multislope ski rental problem, and extend the competitive ratio bound proposed by Lotker et al. to .

In the 3-slope ski-rental problem, the player is asked to determine a strategy, that is, (i) whether to buy a ski wear and then a ski set separately, or to buy them at once for a discount price, and (ii) when to buy these goods. If the player has not got any thing, he/she can rent it for some price. The objective is to minimize the total cost, under the assumption that the player does not know how many times he/she goes skiing in the future. We reveal that even with a large discount for buying at once available, there is some price setting for which to buy the goods separately is a more reasonable choice. We also show that the performance of the optimal strategy may become arbitrarily worse, when a large discount is offered., Article, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E99A(6) : 1075-1083(2016)

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player's performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems., Article, JOURNAL OF COMBINATORIAL OPTIMIZATION. 31(2): 463-490 (2016)

Idling, or running the engine when the vehicle is not moving, accounts for 13%–23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics $\mu _{B^{\tt -}}$ and $q_{B^{\tt +}}$ , the expected length of short stops and the probability of long stops. We develop two online algorithms, a suboptimal closed-form algorithm and an optimal numerical solution, that combine the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the algorithms perform better than existing solutions in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins'' and "requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.

Cloud service providers enable tenants to elastically scale resources to meet their demands. While running cloud applications, a tenant aiming to minimize cost is often challenged with crucial tradeoffs. For instance, upon each arrival of a query, a Web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response to reduce future compute costs. The Ski-Rental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy tradeoff; in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In the multislope version of the Ski-Rental problem, the skier can choose among multiple services that differ in their buying and renting prices. In this paper, we introduce a variant of the classical Ski-Rental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We also extend the classical multislope Ski-Rental problem, where the skier can choose among multiple services, to this setting. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

We consider the following generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. In our generalization, there are two "payment plans" called "options," such that each option i (for i = 1 , 2 ) consists of two kinds of costs: b i is the (one time) cost to start using Option i, and a i is the (ongoing) usage cost per unit of time for Option i. We assume w.l.o.g.?that a 1 a 2 and b 1 < b 2 . Additionally, we assume the existence of a transition cost c, which is incurred if we switch from Option 1 to Option 2. (In the classical version, b 1 = 0 , a 2 = 0 and c = b 2 .)We give deterministic and randomized algorithms for this general setting and analyze their competitive ratio. We also prove that the competitive ratios of our algorithms are the best possible by presenting matching lower bounds for both the deterministic and the randomized cases.

The co-existence of small cell base stations (SBSs) with conventional macrocell base station is a promising approach to boost the capacity and coverage of cellular networks. However, densifying the network with a viral deployment of SBSs can significantly increase energy consumption. To reduce the reliance on unsustainable energy sources, one can adopt self-powered SBSs that rely solely on energy harvesting. Due to the uncertainty of energy arrival and the finite capacity of energy storage systems, self-powered SBSs must smartly optimize their ON and OFF schedule. In this paper, the problem of ON/OFF scheduling of self-powered SBSs is studied, in the presence of energy harvesting uncertainty with the goal of minimizing the operational costs consisting of energy consumption and transmission delay of a network. For the original problem, we show that an algorithm can solve the problem in the illustrative case. Then, to reduce the complexity of the original problem, an approximation is proposed. To solve the approximated problem, a novel approach based on the ski rental framework, a powerful online optimization tool, is proposed. Using this approach, each SBS can effectively decide on its ON/OFF schedule autonomously, without any prior information on future energy arrivals. By using competitive analysis, a deterministic online algorithm and a randomized online algorithm (ROA) are developed. The ROA is then shown to achieve the optimal competitive ratio in the approximation problem. Simulation results show that, compared with a baseline approach, the ROA can yield performance gains reaching up to 15.6% in terms of reduced total energy consumption of SBSs and up to 20.6% in terms of per-SBS network delay reduction. The results also shed light on the fundamental aspects that impact the ON time of SBSs while demonstrating that the proposed ROA can reduce up to 69.9% the total cost compared with a baseline approach.

Current theoretical attempts towards understanding real-life leasing scenarios assume the following leasing model. Demands arrive with time and need to be served by leased resources. Different types of leases are available, each with a fixed duration and price, respecting economy of scale (longer leases cost less per unit time). An online algorithm is to serve each arriving demand while minimizing the total leasing costs and without knowing future demands. In this paper, we generalize this model into one in which lease prices fluctuate with time and are not known to the algorithm in advance. Hence, an online algorithm is to perform under the uncertainty of both demands and lease prices. We consider different adversarial models and provide online algorithms, evaluated using standard competitive analysis. For each of these models, we give deterministic matching upper and lower bounds.

We consider the multi-shop ski rental problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a consumer has to make decisions on when and where to buy. We are interested in the optimal online (competitive-ratio minimizing) mixed strategy from the consumer's perspective. For our problem in its basic form, we obtain exciting closed-form solutions and a linear time algorithm for computing them. We further demonstrate the generality of our approach by investigating three extensions of our basic problem, namely ones that consider costs incurred by entering a shop or switching to another shop. Our solutions to these problems suggest that the consumer must assign positive probability in exactly one shop at any buying time. Our results apply to many real-world applications, ranging from cost management in IaaS cloud to scheduling in distributed computing.

We study several variants of a fixed length ski rental problem and related scheduling problems with rejection. A ski season consists of m days, and an equipment of cost 1 is to be used during these days. The equipment can be bought on any day, in which case it can be used without any additional cost starting that day and until the vacation ends. On each day, the algorithm is informed with the current non-negative cost of renting the equipment. As long as the algorithm did not buy the equipment, it must rent it every day of the vacation, paying the rental cost of each day of rental. We consider the case of arbitrary, non-increasing, and non-decreasing rental costs. We consider the case where the season cannot end before the mth day, and the case that it can end without prior notice. We propose optimal online algorithms for all values of m for all variants. The optimal competitive ratios are either defined by solutions of equations (closed formulas or finite recurrences) or sets of mathematical programs, and tend to 2 as m grows.

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several options of paying both of a per-time fee and an initial fee, in addition to pure renting and buying options. Damaschke gave a lower bound of 3.62 on the competitive ratio for the case where arbitrary number of options can be offered. In this paper we propose a scheme that for the number of options given as an input, provides a lower bound on the competitive ratio, by extending the method of Damaschke. This is the first to establish a lower bound for each of the 5-or-more-option cases, for example, a lower bound of 2.95 for the 5-option case, 3.08 for the 6-option case, and 3.18 for the 7-option case. Moreover, it turns out that our lower bounds for the 3- and 4-option cases respectively coincide with the known upper bounds. We therefore conjecture that our scheme in general derives a matching lower and upper bound., Article, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E97A(6): 1200-1205 (2014)

In this paper, we consider the application of revenue management techniques in the context of the car rental industry. In particular, the paper presents a dynamic programming formulation for the problem of assigning cars of several categories to different segments of customers, with rental requests arising dynamically and randomly with time. Customers make a rental request for a given type of car, for a given number of days at a given pickup time. The rental firm can satisfy the demand for a given product with either the product requested or with a car of at most one category superior to that initially required, in this case an “upgrade” can take place. The one-way rental scenario, which allows the possibility of the rental starting and ending at different locations, is also addressed. In the framework considered, the logistic operator has to decide whether to accept or reject a rental request. Since the proposed dynamic programming formulations are impractical due to the curse of dimensionality, linear programming approximations are used to derive revenue management decision policies for the operator. Indeed, primal and dual acceptance policies are developed (i.e. booking limits, bid prices) and their effectiveness is assessed on the basis of an extensive computational phase.

The viral and dense deployment of small cell base stations (SBSs) will lie at the heart of 5G cellular networks. However, such dense networks can consume a significant amount of energy. In order to reduce the network's reliance on unsustainable energy sources, one can deploy self-powered SBSs that rely solely on energy harvesting. Due to the uncertainty of energy arrival and the finite capacity of energy storage systems, self-powered SBSs must smartly schedule their ON and OFF operation. In this paper, the problem of ON/OFF scheduling of self-powered SBSs is studied in the presence of energy harvesting uncertainty with the goal of minimizing the tradeoff between power consumption and flow-level delay. To solve this problem, a novel approach based on the ski rental framework, a powerful online optimization tool, is proposed. To find the desired solution of the ski rental problem, a randomized online algorithm is developed to enable each SBS to autonomously decide on its ON/OFF schedule, without knowing any prior information on future energy arrivals. Simulation results show that the proposed algorithm can reduce power consumption and delay over a given time period compared to a baseline that turns SBSs ON by using an energy threshold. The results show that this performance gain can reach up to 12.7% reduction of the total cost. The results also show that the proposed algorithm can eliminate up to 72.5% of the ON/OFF switching overhead compared to the baseline approach.

This article describes the development of a new heuristic algorithm which guarantees an optimal solution for specially structured flow shop problem with n-jobs,3- machines, to minimize the rental cost under specified rental policy in which set up times are separated from processes time, including transformation time. Further the processing times are not merely random but bear a well defined relationship to one another. Most of literature emphasized on minimization of idle time/ make span. But minimization of make span may not always lead to minimize rental cost of machines. Objective of this work is to minimize the rental cost of machines under a specified rental policy irrespective of make span.

We introduce the continuously compounded interest rate into a generalized ski-rental problem with two options: either pay some rental proportionally to the usage time (the rent option), or buy the equipment and then pay some reduced rental proportionally to the usage time (the generalized buy option). Under the framework of competitive analysis, a randomized algorithm for the modified model is constructed and then is proved optimal by Yao@?s Lemma, and thus the optimal competitive ratio is obtained. The result shows that the introduction of the interest rate puts off the optimal purchase date and diminishes the uncertainty involved in the decision making.

The present paper considers a more practical problem of scheduling n jobs in a two machine specially structured open shop to minimize the rental cost. Further the processing time of jobs is associated with their respective probabilities including transportation time. In most of literature the processing times are always considered to be random, but there are significant situations in which processing times are not merely random but bear a well defined structural relationship to one another. The objective of this paper is to minimize the rental cost of machines under a specified rental policy. The algorithm is demonstrated through the numerical illustration.

Content Delivery Networks (CDNs) deliver web content to end-users from a large distributed platform of web servers hosted in data centers belonging to thousands of Internet Service Providers (ISPs) around the world. The bandwidth cost incurred by a CDN is the sum of the amounts it pays each ISP for routing traffic from its servers located in that ISP out to end-users. A large enterprise may also contract with multiple ISPs to provide redundant Internet access for its origin infrastructure using technologies such as multihoming and mirroring, thereby incurring a significant bandwidth cost across multiple ISPs. This paper initiates the formal algorithmic study of bandwidth cost minimization in the context of a large enterprise or a CDN, a problem area that is both algorithmically rich and practically very important. First, we model different types of contracts that are used in practice by ISPs to charge for bandwidth usage, including average, maximum, and 95th-percentile contracts. Then, we devise an optimal offline algorithm that routes traffic to achieve the minimum bandwidth cost, when the network contracts charge either on a maximum or on an average basis. Next, we devise a deterministic (resp., randomized) online algorithm that achieves cost that is within a factor of 2 (resp., ee-1) of the optimal offline cost for maximum and average contracts. In addition, we prove that our online algorithms achieve the best possible competitive ratios in both the deterministic and the randomized cases. An interesting theoretical contribution of this work is that we show intriguing connections between the online bandwidth optimization problem and the seemingly-unrelated but well-studied ski rental problem where similar optimal competitive ratios are known to hold. Finally, we consider extensions for contracts with a committed amount of spend (known as committed information rate or CIR) and contracts that charge on a 95th-percentile basis.

We define and solve a simple extension of the ski-rental problem [A.R. Karlin, M.S. Manasse, L. Rudolph, D.D. Sleator, Competitive snoopy caching, Algorithmica 3 (1) (1988) 77-119]. In the classical version, the algorithm needs to decide when to switch from renting to buying. In our version, no pure buy option is available: even after switching to the buy option, the algorithm needs to pay some reduced rent.

In cloud computing, users scale their resources (computational) based on their need. There is massive literature dealing with such resource scaling algorithms. These works ignore a fundamental constrain imposed by all Cloud Service Providers (CSP), i.e. one has to pay for a fixed minimum duration irrespective of their usage. Such quantization in billing cycles poses problem for users with sporadic workload. In recent literature, Cloud Broker (CB) has been introduced for the benefit of such users. A CB rents resources from CSP and in turn provides service to users to generate profit. Contract between CB and user is that of pay-what-you-use/pay-per-use. However CB faces the challenge of Quantized Billing Cycles as it negotiates with CSP. We design two algorithms, one fully online and the other partially online, which maximizes the profit of the CB. The key idea is to regulate users demand using dynamic pricing. Our algorithm is inspired by the Ski-Rental problem. We derive competitive ratio of these algorithms and also conduct simulations using real world traces to prove the efficiency of our algorithm., Comment: 11 pages, 9 figures

We present the first optimal randomized online algorithms for the TCP acknowledgment problem [3] and the Bahncard problem [5]. These problems are well known to be generalizations of the classical online ski-rental problem, however, they appeared to be harder. In this paper we demonstrate that a number of online algorithms which have optimal competitive ratios of e/(e-1) , including these, are fundamentally no more complex than ski rental. Our results also suggest a clear paradigm for solving ski-rental-like problems.

Idling, or running the engine when the vehicle is not moving, accounts for 13% - 23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics μB− and qB+, the expectation of short stops' lengths and the probability of long stops. We develop an online algorithm that combines the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the robustness of the algorithm in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

The Ski Rental problem is the canonical example of a class of online rent or buy problems [9]. In the traditional ski rental problem, a man visits a ski resort, not knowing how many days he will be able to ski. The man can either rent skis at a cost of r dollars per day, or buy the skis permanently for b dollars. The dilemma arises from the fact that the number of days available for skiing is not known in advance; if there are many days of skiing it is better to buy the skis to avoid paying the rental fee every day, but if there are only a few days available for skiing it may be more economical to rent the skis instead. Applications of the ski-rental problem include scheduling tasks on a computer (the system must decide if it should do a task immediately by paying a high cost in processing time, or if it should wait and pay a ‘rental’ cost for keeping the task in waiting)[7] and caching data (the system decides if it should read a block of data during every pass at a cost of 1 bus cycle, or if it should pass over the data block and use several bus cycles to access the data if it is needed later) [5]. Several extensions of the Ski Rental problem have already been studied, including variants where the player can switch bewteen two renting options at a cost [3], and more complex scenarios where there are more than two options to choose between [6]. In these cases, an e-competitive algorithm can be found. A natural extension of these situations where there are multiple renting and multiple buying options has also been studied [1]. Algorithms have also been developed to provide a strategy when the rental cost r is free to vary with time [2]. Another more complex extension studied is how to allocate capacity available through renting or buying to a graph’s edges to allow for sufficient flow between sources and sinks [4]. These variants add complexity to the ski rental problem, and as a result the competitive ratio varies as a function of the new parameters introduced by each variation. We consider a generalization of the ski-rental problem where demand varies across time. The motivation for solving this problem is the idea of cloud bursting that is used to address the computing

Empty repositions are a major problem for car rental companies that deal with special types of vehicles whose number of units is small. In order to meet reservation requirements concerning time and location, companies are forced to transfer cars between rental stations, bearing significant costs and increasing the environmental impact of their activity due to the fuel consumption and CO 2 emission. In this paper, this problem is tackled under a vehicle-reservation assignment framework as a network-flow model in which the profit is maximized. The reservations are allocated considering the initial and future availability of each car, interdependencies between rental groups, and different reservation priorities. To solve this model, a relax-and-fix heuristic procedure is proposed, including a constraint based on local branching that enables and controls modifications between iterations. Using real instances, the value of this approach is established and an improvement of 33% was achieved when compared to the company’s current practices.

Consider an on-line player who needs some equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is determined whether the player will need the equipment during the current period and the player has two options: to pay a leasing fee c and rent the equipment for the period, or to buy it for a larger amount P. The total cost incurred by the player is the sum of all leasing fees and perhaps one purchase. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attention in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive performance is achieved by leasing for the first ki 1 times and then buying, where kD P=c. This strategy pays at most 2i 1=k times the optimal off-line cost. When considering alternative financial transactions one must consider their net present value. Thus, ac- counting for the interest rate is an essential feature of any reasonable financial model. In this paper we deter- mine both deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor reduces the uncertainty involved. We find that the optimal deterministic competitive ratio is 1C.1C i/.1i 1=k/.1i k.i=1C i//, a decreasing function of the interest i (for all reasonable values of i ). For some applications, realistic values of interest rates result in relatively low competitive ratios. By using randomization the on-line player can further boost up the performance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller compet- itive ratio of 2i..k=.ki 1// ∞ i 2/=..k=.ki 1// ∞ i 1/ where∞D ln.1i k.1i 1=.1C i///=ln.1=.1C i//. Here again, this competitive ratio strictly decreases with i . We also study the leasing problem against a distributional adversary called "Nature." This adversary chooses the probability distribution of the number of leasing periods and announces this distribution before the on-line player chooses a strategy. Although at the outset this adversary appears to be weaker than the oblivious adversary, it is shown that the optimal competitive ratio against Nature equals the optimal ratio against the oblivious adversary.

The present paper considers a more practical problem of scheduling n jobs in a two machine specially structured open shop to minimize the rental cost. Further the processing time of jobs are associated with their respective probabilities including job block criteria. In most of literature the processing times are always considered to be random, but there are significant situations in which processing times are not merely random but bear a well defined structural relationship to one another. The objective of this paper is to minimize the rental cost of machines under a specified rental policy. A numerical illustration is given to support the algorithm.

Optimization has been used extensively throughout signal processing in applications including sensor networks and sparsity based compressive sensing. One of the key challenges when implementing iterative optimization algorithms is to choose an appropriate step size for fast algorithms. We pose the problem of choosing step sizes as solving a ski rental problem, a popular class of problems from the computer science literature. This results in a novel algorithm for adaptive step size selection that is agnostic to the choice of the optimization algorithm. Our numerical results show the advantages of using adaptivity for step size selection.

Cloud service providers (CSPs) enable tenants to elastically scale their resources to meet their demands. In fact, there are various types of resources offered at various price points. While running applications on the cloud, a tenant aiming to minimize cost is often faced with crucial trade-off considerations. For instance, upon each arrival of a query, a web application can either choose to pay for CPU to compute the response fresh, or pay for cache storage to store the response so as to reduce the compute costs of future requests. The SkiRental problem abstracts such scenarios where a tenant is faced with a to-rent-or-to-buy trade-off; in its basic form, a skier should choose between renting or buying a set of skis without knowing the number of days she will be skiing. In this paper, we introduce a variant of the classical SkiRental problem in which we assume that the skier knows the first (or second) moment of the distribution of the number of ski days in a season. We demonstrate that utilizing this information leads to achieving the best worst-case expected competitive ratio (CR) performance. Our method yields a new class of randomized algorithms that provide arrivals-distribution-free performance guarantees. Further, we apply our solution to a cloud file system and demonstrate the cost savings obtained in comparison to other competing schemes. Simulations illustrate that our scheme exhibits robust average-cost performance that combines the best of the well-known deterministic and randomized schemes previously proposed to tackle the Ski-Rental problem.

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several options of paying both of a per-time fee and an initial fee, in addition to pure renting and buying options. Damaschke gave a lower bound of 3.62 on the competitive ratio for the case where arbitrary number of options can be offered. In this paper we propose a scheme that for the number of options given as an input, provides a lower bound on the competitive ratio, by extending the method of Damaschke. This is the first to establish a lower bound for each of the 5-or-more-option cases, for example, a lower bound of 2.95 for the 5-option case, 3.08 for the 6-option case, and 3.18 for the 7-option case. Moreover, it turns out that our lower bounds for the 3- and 4-option cases respectively coincide with the known upper bounds. We therefore conjecture that our scheme in general derives a matching lower and upper bound.

We study several variants of a fixed length ski rental problem and related scheduling problems with rejection. A ski season consists of m days, and an equipment of cost 1 is to be used during these days. The equipment can be bought on any day, in which case it can be used without any additional cost starting that day and until the vacation ends. On each day, the algorithm is informed with the current non-negative cost of renting the equipment. As long as the algorithm did not buy the equipment, it must rent it every day of the vacation, paying the rental cost of each day of rental. We consider the case of arbitrary, non-increasing, and non-decreasing rental costs. We consider the case where the season cannot end before the mth day, and the case that it can end without prior notice. We propose optimal online algorithms for all values of m for all variants. The optimal competitive ratios are either defined by solutions of equations (closed formulas or finite recurrences) or sets of mathematical programs, and tend to 2 as m grows.

We consider a generalization of the classical problem of ski rental. There is a game that ends at an unknown time, and the algorithm needs to decide how to pay for the time until the game ends. There are two "payment plans" or "options," such that the cost of t time units under option i (for i = 1,2) is given by a i t + b i , where b i is a one-time cost to start using option i, and a i is the ongoing cost per time unit. We assume w.l.o.g. that a 1 > a 2 and b 1 < b 2. (The classical version is b 1 = 0 and a 2 = 0, so that option 1 is "pure rent" and option 2 is "pure buy.") We give deterministic and randomized algorithms for the general setting and prove matching lower bounds on the competitive ratios for the problem. This is the first non-trivial result for the non-additive model of ski rental, which models non-refundable one-time costs.

Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approachinge/(eź1) ź 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approachinge/(eź1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approache/(eź1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.

We extend the classic online ski rental problem, so that the rental price may change over time. We consider several models which differ in the knowledge given to the algorithm: whereas the price development is unknown, an algorithm may have full, partial or no knowledge about the duration of the game. We construct algorithms whose competitive ratios are up to constant or logarithmic factors optimal.

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.

The Bahncard problem can be viewed as a generalization of the Ski-Rental problem. The simplified Bahncard problem is the special case that the Bahncard never expires. When considering alternative financial transaction one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper, both the interest rate factor and risk management are introduced to this special case, the introduction of these parameters considerably improve the performance measure of competitive analysis.

The special Bahncard problem is a generalization of the Ski-Rental problem. In this paper, average-case competitive analysis which integrates probability distribution into pure competitive analysis is employed to restudy this problem. Theoretical and numerical results show that the performance measure of competitive analysis can be dramatically improved. Moreover, we study the special Bahncard problem with interest rate which should be considered in any reasonable financial model. The optimal deterministic competitive ratio is obtained and the competitive ratio C(k) decreases with the interest rate i.

Content delivery networks (CDNs) deliver Web content to end-users from a large distributed platform of Web servers hosted in data centers belonging to thousands of Internet service providers (ISPs) around the world. The bandwidth cost incurred by a CDN is the sum of the amounts it pays each ISP for routing traffic from its servers located in that ISP out to end-users. A large enterprise may also contract with multiple ISPs to provide redundant Internet access for its origin infrastructure using technologies such as multihoming and mirroring, thereby incurring a significant bandwidth cost across multiple ISPs. This paper initiates the formal study of bandwidth cost minimization in the context of a large enterprise or a CDN, a problem area that is both algorithmically rich and practically very important. First, we model different types of contracts that are used in practice by ISPs to charge for bandwidth usage, including average, maximum, and 95th-percentile contracts. Then, we devise an optimal offline algorithm that routes traffic to achieve the minimum bandwidth cost, when the network contracts charge either on a maximum or on an average basis. Next, we devise a deterministic (resp., randomized) online algorithm that achieves cost that is within a factor of 2 (resp., e/(e - 1)) of the optimal offline cost for maximum and average contracts. In addition, we prove that our online algorithms achieve the best possible competitive ratios in both the deterministic and the randomized cases. An interesting theoretical contribution of this work is that we show intriguing connections between the online bandwidth optimization problem and the seemingly-unrelated but well-studied ski rental problem where similar optimal competitive ratios are known to hold. Finally, we consider extensions for contracts with a committed amount of spend (CIRs) and contracts that charge on a 95th-percentile basis

We consider online problems where purchases have time durations which expire regardless of whether the purchase is used or not. The parking permit problem is the natural analog of the well-studied ski rental problem in this model, and we provide matching upper and lower bounds on the competitive ratio for this problem. By extending the techniques thus developed, we give an online-competitive algorithm for the problem of renting steiner forest edges with time durations.