Tight approximation for unconstrained XOS maximization

DOI10.1287/MOOR.2020.1088MaRDI QIDQ5026453zbMATH OpenOpenAlexFDO

Authors Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi

Publication date 8 February 2022

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.09045

zbMATH Keywords

approximation algorithmsvalue oraclesXOS functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width $1$ because they are just additive, but it is already nontrivial even when the width is restricted to $2$. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between $O(n)$ and $Omega(n/logn)$, and exactly $Theta(n/logn)$ if randomization is allowed, where $n$ is the ground set size. Second, when the width of the input XOS functions is bounded by a constant $kgeq2$, the approximation bound is between $k-1$ and $k-1-epsilon$ for any $epsilon>0$. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width $2$, while we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to $3$.

Recommendations

• Optimal bounds on approximation of submodular and XOS functions by juntas
• Maximizing Non-monotone Submodular Functions
• Fast algorithms for maximizing submodular functions
• Adaptivity gaps for stochastic probing: submodular and XOS functions
• Maximizing a monotone submodular function subject to a matroid constraint

Cites work

• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A note on maximizing a submodular set function subject to a knapsack constraint
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An analysis of approximations for maximizing submodular set functions—I
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Combinatorial auctions with decreasing marginal utilities
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
• Deterministic Algorithms for Submodular Maximization Problems
• Geometric algorithms and combinatorial optimization
• Maximizing Non-monotone Submodular Functions
• Maximizing a monotone submodular function subject to a matroid constraint
• On maximizing welfare when utility functions are subadditive
• The asymptotic number of geometries
• The ellipsoid method and its consequences in combinatorial optimization
• Walrasian equilibrium with gross substitutes

This page was built for publication: Tight approximation for unconstrained XOS maximization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5026453)