Tight Approximation for Unconstrained XOS Maximization

Yuval Filmus (), Yasushi Kawase (), Yusuke Kobayashi () and Yutaro Yamaguchi ()
Additional contact information
Yuval Filmus: The Henry and Marilyn Taub Faculty of Computer Science, Technion–Israel Institute of Technology, Haifa 3200003, Israel
Yasushi Kawase: Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, Japan
Yusuke Kobayashi: Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
Yutaro Yamaguchi: Graduate School and Faculty of Information Science and Electrical Engineering, Kyushu University, Fukuoka 819-0395, Japan

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1599-1610

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 Ω ( n / l o g n ) , and exactly θ ( n / l o g n ) 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 k ≥ 2, the approximation bound is between k − 1 and k − 1 − ɛ for any ɛ > 0. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width 2, whereas we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to 3.

Keywords: Primary: 90C27; secondary: 68W25; 68Q25; Primary: analysis of algorithms: computational complexity; secondary: mathematics: combinatorics; XOS functions; value oracles; approximation algorithms (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1088 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:4:p:1599-1610

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().