Tight Approximation for Unconstrained XOS Maximization

DOI10.1287/moor.2020.1088zbMath1484.90092arXiv1811.09045OpenAlexW3143775817MaRDI QIDQ5026453

Yuval Filmus, Yutaro Yamaguchi, Yasushi Kawase, Yusuke Kobayashi

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)

Cites Work

• Unnamed Item
• Unnamed Item
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Walrasian equilibrium with gross substitutes
• The asymptotic number of geometries
• A note on maximizing a submodular set function subject to a knapsack constraint
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial auctions with decreasing marginal utilities
• Maximizing Non-monotone Submodular Functions
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Deterministic Algorithms for Submodular Maximization Problems
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• On Maximizing Welfare When Utility Functions Are Subadditive
• Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid

This page was built for publication: Tight Approximation for Unconstrained XOS Maximization