Abstract
We consider the online vector packing problem in which we have a d dimensional knapsack and items u with weight vectors w_u in R_+^d arrive online in an arbitrary order. Upon the arrival of an item, the algorithm must decide immediately whether to discard or accept the item into the knapsack. When item u is accepted, w_u(i) units of capacity on dimension i will be taken up, for each i in [d]. To satisfy the knapsack constraint, an accepted item can be later disposed of with no cost, but discarded or disposed of items cannot be recovered. The objective is to maximize the utility of the accepted items S at the end of the algorithm, which is given by f(S) for some nonnegative monotone submodular function f.
For any small constant epsilon > 0, we consider the special case that the weight of an item on every dimension is at most a (1 epsilon) fraction of the total capacity, and give a polynomialtime deterministic O(k / epsilon^2)competitive algorithm for the problem, where k is the (column) sparsity of the weight vectors. We also show several (almost) tight hardness results even when the algorithm is computationally unbounded. We first show that under the epsilonslack assumption, no deterministic algorithm can obtain any o(k) competitive ratio, and no randomized algorithm can obtain any o(k / log k) competitive ratio. We then show that for the general case (when epsilon = 0), no randomized algorithm can obtain any o(k) competitive ratio.
In contrast to the (1+delta) competitive ratio achieved in Kesselheim et al. [STOC 2014] for the problem with random arrival order of items and under large capacity assumption, we show that in the arbitrary arrival order case, even when w_u_infinity is arbitrarily small for all items u, it is impossible to achieve any o(log k / log log k) competitive ratio.
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2017:7819,
author = {T.H. Hubert Chan and Shaofeng H.C. Jiang and Zhihao Gavin Tang and Xiaowei Wu},
title = {{Online Submodular Maximization Problem with Vector Packing Constraint}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {24:124:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7819},
URN = {urn:nbn:de:0030drops78190},
doi = {10.4230/LIPIcs.ESA.2017.24},
annote = {Keywords: Submodular Maximization, Freedisposal, Vector Packing}
}
Keywords: 

Submodular Maximization, Freedisposal, Vector Packing 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017) 
Issue Date: 

2017 
Date of publication: 

31.08.2017 