NDLI: The multi-shop ski rental problem

Please wait, while we are loading the content...

Rumor source detection with multiple observations: fundamental limits and algorithms

An online auction framework for dynamic resource provisioning in cloud computing

Index policies for a multi-class queue with convex holding cost and abandonments

Conquering big data with spark and BDAS

Hershel: single-packet os fingerprinting

The behavior of epidemics under bounded susceptibility

Tunable survivable spanning trees

GemDroid: a framework to evaluate mobile platforms

Pricing link by time

CApRI: CAche-conscious data reordering for irregular codes

On the energy and performance of commodity hardware transactional memory

Scheduling using interactive oracles: connection between iterative optimization and low-complexity scheduling

Collecting, organizing, and sharing pins in pinterest: interest-driven or social-driven?

Energy procurement strategies in the presence of intermittent sources

Concave switching in single and multihop networks

Noise can help: accurate and efficient per-flow latency measurement without packet probing and time stamping

Studying social networks at scale: macroscopic anatomy of the twitter social graph

Balanced resource allocations across multiple dynamic MapReduce clusters

Understanding the impact of network dynamics on mobile video user engagement

Serving content with unknown demand: the high-dimensional regime

Neighbor-cell assisted error correction for MLC NAND flash memories

Impact of correlated mobility and cluster scalability on connectivity of wireless networks

Unified localization framework using trajectory signatures

Jointly clustering rows and columns of binary matrices: algorithms and trade-offs

Randomized auction design for electricity markets between grids and microgrids

The power of online learning in stochastic network optimization

A measurement study of google play

Stochastic bandits with side observations on networks

On the relevance of adversarial queueing theory in practice

Error estimating codes for insertion and deletion channels

Network-design sensitivity analysis

ANATOMY: an analytical model of memory system performance

Unleashing the potentials of dynamism for page allocation strategies in SSDs

TS-CLOCK: temporal and spatial locality aware buffer replacement algorithm for NAND flash storages

Filter & follow: how social media foster content curation

Pricing data center demand response

Is sharing with retransmissions causing instabilities?

IntroPerf: transparent context-sensitive multi-layer performance inference using system stack traces

On maximizing diffusion speed in social networks: impact of random seeding and clustering

Data dissemination performance in large-scale sensor networks

The multi-shop ski rental problem

The efficacy of error mitigation techniques for DRAM retention failures: a comparative experimental study

Traffic congestion: models, costs and optimal transport

Multi-source multipath HTTP (mHTTP): a proposal

Privacy tradeoffs in predictive analytics

Non-work-conserving effects in MapReduce: diffusion limit and criticality

Non-intrusive, out-of-band and out-of-the-box systems monitoring in the cloud

Movers and shakers: kinetic energy harvesting for the internet of things

GDM: device memory management for gpgpu computing

Randomized routing schemes for large processor sharing systems with multiple service rates

Performance analysis of MAC for power-line communications

Automated analysis of multithreaded programs for performance modeling

Impact of DHCP churn on network characterization

A comparison of core power gating strategies implemented in modern hardware

Online algorithms for joint application-VM-physical-machine auto-scaling in a cloud

Topic modeling from network spread

Distributed optimal load shedding for disaster recovery in smart electric power grids: a second-order approach

BATS: budget-constrained autoscaling for cloud performance optimization

TARDIS: stably shifting traffic in space and time

What's your choice?: learning the mixed multi-nomial

Exact analysis of TTL cache networks: the case of caching policies driven by stopping times

Revisiting caching in content delivery networks

Measuring throughput of data center network topologies

FLOWR: a self-learning system for classifying mobileapplication traffic

Efficient task replication for fast response times in parallel computation

Accurate and robust time reconstruction for deployed sensor networks

Effect of proactive serving on user delay reduction in service systems

Optimal energy source selection and capacity planning for green datacenters

The multi-shop ski rental problem

Content Provider	ACM Digital Library
Author	Ai, Lingqing Huang, Lingxiao Tang, Pingzhong Li, Jian Wu, Xian Huang, Longbo
Abstract	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.
Starting Page	463
Ending Page	475
Page Count	13
File Format	PDF
ISBN	9781450327893
DOI	10.1145/2591971.2591984
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Optimal strategy Nash equilibrium Online algorithm Ski rental Multi-shop ski rental
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in