Zip.ca is an online DVD rental company that faces two major operational problems:
calculation of the assignment of DVDs to customers every thirty minutes
throughout the day and purchasing of new inventory in regular intervals.
In this thesis, we model these two problems and develop algorithms to solve
them. In doing so, we encounter many theoretical problems that are both applicable
to Zip’s operations and intrinsically interesting problems independent of the
application.
First, we note that the assignment problem facing Zip is inherently in an online
setting. With returns of DVDs being processed throughout the day, the dataset
is constantly changing. Although the ideal solution would be to wait until the
end of the day to make decisions, physical work load capacities prevent this. For
this reason we discuss two online problems, online 0-1 budgeted matching and
the budgeted Adwords auction. We present a 1/(2 w_max/w_min)-competitive algorithm for the online 0-1 budgeted matching problem, and prove that this is the best possible
competitive ratio possible for a wide class of algorithms. We also give a (1− (S+1)/(S+e) )-competitive algorithm for the budgeted Adwords auction as the size of the bids
and cost get small compared to the budgets, where S is the ratio of the highest and
lowest ratios of bids to costs.
We suggest a linear programming approach to solve Zip’s assignment problem.
We develop an integer program that models the B-matching instance with additional
constraints of concern to Zip, and prove that this integer program belongs to
a larger class of integer programs that has totally unimodular constraint matrices.
Thus, the assignment problem can be solved to optimality every thirty minutes.
We additionally create a test environment to check daily performance, and provide
real-time implementation results, showing a marked improvement over Zip’s old
algorithm.
We show that Zip’s purchasing problem can be modeled by the matching augmentation
problem defined as follows. Given a graph with vertex capacities and
costs, edge weights, and budget C, find a purchasing of additional node capacity of
cost at most C that admits a B-matching of maximum weight. We give a PTAS for
this problem, and then present a special case that is polynomial time solvable that
still models Zip’s purchasing problem, under the assumption of uniform costs.
We then extend the augmentation idea to matroids and present matroid augmentation,
matroid knapsack, and matroid intersection knapsack, three NP-hard
problems. We give an FPTAS for matroid knapsack by dynamic programming,
PTASes for the other two, and demonstrate applications of these problems.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/4666 |
| Date | January 2009 |
| Creators | Pearson, James Ross |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.003 seconds