External authors:

• Javier Marinkovic ( Universidad de Chile , University of Maryland College Park )
• Jose A. Soto ( Universidad de Chile )

Abstract:

We consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an item to be sold, and every edge represents a bundle of items. For combinatorial auctions, Kesselheim et al. showed upper bounds of O(loglog(k)/log(k))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log \log (k)/\log (k))$$\end{document} and O(loglog(n)/log(n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log \log (n)/\log (n))$$\end{document} on the competitiveness of any online algorithm, even in the random order model, where k is the maximum bundle size and n is the number of items. We provide an exponential improvement by giving upper bounds of O(log(k)/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log (k)/k)$$\end{document}, and O(log(n)/n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log (n)/\sqrt{n})$$\end{document} for the prophet IID setting. Furthermore, using linear programming, we provide new and improved guarantees for the k-bounded online combinatorial auction problem (i.e., bundles of size at most k). We show a (1-e-k)/k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-e<^>{-k})/k$$\end{document}-competitive algorithm in the prophet IID model, a 1/(k+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/(k+1)$$\end{document}-competitive algorithm in the prophet-secretary model using a single sample per agent, and a k-k/(k-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k<^>{-k/(k-1)}$$\end{document}-competitive algorithm in the secretary model. Our algorithms run in polynomial time and work in more general independence systems where the offline combinatorial assignment problem admits the existence of a polynomial-time randomized algorithm that we call certificate sampler. These systems include some classes of matroids, matroid intersections, and matchoids.