Xiaoqi Tan

Talk's Abstract: In this talk, we present our recent progress on a new variant of knapsack problems, termed as online knapsack problems with convex packing costs. In this problem, a set of items, each with a value and a weight, appear in a sequential and arbitrary manner. Upon the arrival of each item, an irrevocable decision must be made in terms of whether to pack this item or not into the knapsack with a limited capacity. If an item is accepted, the knapsack incurs a packing cost which depends on the total weight of items that are currently being included in the knapsack, namely, a weight-dependent packing cost. The objective is to (approximately) maximize the social welfare, i.e., the total value of accepted items minus the packing cost. We study this problem under the framework of competitive analysis. The major contribution of our work is the development of a unified approach that achieves the best-possible competitive ratios for settings with different packing costs. Specifically, in the talk we will show that when there is no packing cost or the packing cost is linear, our model is essentially a standard 0-1 knapsack problem, for which our approach achieves logarithmic competitive ratios that match the state-of-the-art (which is optimal). For the more challenging setting when the packing cost is strictly-convex, we provide online algorithms, for the first time, that lead to optimal competitive ratios as well. To the best of our knowledge, this is the first approach that unifies the characterization of optimal competitive ratios for online knapsack problems with either zero, linear, or strictly-convex packing costs. We validate the theoretic results via empirical studies of online resource allocation in cloud computing. Our numerical results demonstrate that the proposed online algorithm is robust against arrival uncertainties and outperforms several existing benchmarks.

Biography:

Xiaoqi Tan is currently a postdoctoral fellow at The Edward S. Rogers Sr. Department of Electrical and Computer Engineering, University of Toronto, Canada. Prior to the current position, he received his Ph.D. degree in electronic and computer engineering from the Hong Kong University of Science and Technology in 2018. From October 2015 to April 2016, he was a visiting research fellow with the School of Engineering and Applied Science, Harvard University. His research broadly lies at the intersection of online algorithms, algorithmic game theory, and mechanism design, with a focus on applications in the design and analysis of computing, networked, and energy systems.

Email:

Address:University of Toronto, , Toronto, Ontario, Canada