Online Submodular Maximization Problem with Vector Packing Constraint Article Swipe

MAKE IMPACT

T-H. Hubert Chan , Shaofeng H.-C. Jiang , Zhihao Gavin Tang , Xiaowei Wu · YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.48550/arxiv.1706.06922

We consider the online vector packing problem in which we have a $d$ dimensional knapsack and items $u$ with weight vectors $\mathbf{w}_u \in \mathbb{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, $\mathbf{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 non-negative monotone submodular function $f$. For any small constant $ε> 0$, we consider the special case that the weight of an item on every dimension is at most a $(1-ε)$ fraction of the total capacity, and give a polynomial-time deterministic $O(\frac{k}{ε^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 show that under the $ε$-slack assumption, no deterministic algorithm can obtain any $o(k)$ competitive ratio, and no randomized algorithm can obtain any $o(\frac{k}{\log k})$ competitive ratio. For the general case (when $ε= 0$), no randomized algorithm can obtain any $o(k)$ competitive ratio. In contrast to the $(1+δ)$ 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 $\| \mathbf{w}_u \|_\infty$ is arbitrarily small for all items $u$, it is impossible to achieve any $o(\frac{\log k}{\log\log k})$ competitive ratio.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/1706.06922

PDF

https://arxiv.org/pdf/1706.06922

OA Status

green

Cited By

6

References

18

Related Works

10

OpenAlex ID

https://openalex.org/W2682688796

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W2682688796

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.1706.06922

Digital Object Identifier

Title

Online Submodular Maximization Problem with Vector Packing Constraint

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2017

Year of publication

Publication date

2017-06-21

Full publication date if available

Authors

T-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, Xiaowei Wu

List of authors in order

Landing page

https://arxiv.org/abs/1706.06922

Publisher landing page

PDF URL

https://arxiv.org/pdf/1706.06922

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/1706.06922

Direct OA link when available

Concepts

Knapsack problem, Submodular set function, Combinatorics, Deterministic algorithm, Dimension (graph theory), Mathematics, Competitive analysis, Monotone polygon, Packing problems, Randomized algorithm, Online algorithm, Function (biology), Maximization, Constraint (computer-aided design), Approximation algorithm, Order (exchange), Discrete mathematics, Fraction (chemistry), Mathematical optimization, Upper and lower bounds, Finance, Evolutionary biology, Mathematical analysis, Biology, Geometry, Organic chemistry, Chemistry, Economics

Top concepts (fields/topics) attached by OpenAlex

Cited by

6

Total citation count in OpenAlex

Citations by year (recent)

2021: 2, 2020: 1, 2019: 1, 2018: 1, 2017: 1

Per-year citation counts (last 5 years)

References (count)

18

Number of works referenced by this work

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload