Library

Notes: Abstract. 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 k-1 times and then buying, where k = P/c . This strategy pays at most 2-1/k times the optimal off-line cost. When considering alternative financial transactions 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 we determine 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 1 + (1+i)(1-1/k)(1 - k(i/1+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 competitive ratio of 2 - ( (k/(k-1)) γ - 2 )/( (k/(k-1)) γ -1 ) where γ = ln ( 1 - k(1 - 1/(1+i)) ) / ln(1/(1+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.

Notes: Abstract We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.

Notes: Abstract We give various characterizations ofk-vertex connected graphs by geometric, algebraic, and “physical” properties. As an example, a graphG isk-connected if and only if, specifying anyk vertices ofG, the vertices ofG can be represented by points of ℝk−1 so that nok are on a hyper-plane and each vertex is in the convex hull of its neighbors, except for thek specified vertices. The proof of this theorem appeals to physics. The embedding is found by letting the edges of the graph behave like ideal springs and letting its vertices settle in equilibrium. As an algorithmic application of our results we give probabilistic (Monte-Carlo and Las Vegas) algorithms for computing the connectivity of a graph. Our algorithms are faster than the best known (deterministic) connectivity algorithms for allk≧√n, and for very dense graphs the Monte Carlo algorithm is faster by a linear factor.

Notes: Abstract We consider a simple abstract model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string ofn bits and is a “success” or “failure” depending on whether the string produced belongs to a prespecified setL. In an uninfluenced process each bit is chosen by a fair coin toss, and hence the probability of success is ¦L¦/2 n . A player called the controller, is introduced who has the ability to intervene in the process by specifying the value of some of the bits of the string. We answer the following questions for both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of ¦L¦what is the expected number of interventions needed to guarantee success? In particular our results imply that if ¦L¦/2 n =1/Ω(n) where Ω(n) tends to infinity withn (so the probability of success with no interventions is 0(1)) then withO(√n logΩ(n)) interventions the probability of success is 1−0(1). Our main results and the proof techniques are related to well-known results of Kruskal, Katona and Harper in extremal set theory.