Optimization with Uniform Size Queries

Consider the problem of selecting k items that maximize the value of a monotone submodular set function f , where f can be accessed using value queries. It is well known that polynomially many queries suffice in order to obtain an approximation ratio of 1 - 1 e . We consider a variation on this prob...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2017-05, Vol.78 (1), p.255-273
Main Authors: Feige, Uriel, Tennenholtz, Moshe
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Approximation
Buoyancy
Clients
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Functions (mathematics)
Mathematical analysis
Mathematics of Computing
Queries
Ratios
Silicon
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider the problem of selecting k items that maximize the value of a monotone submodular set function f , where f can be accessed using value queries. It is well known that polynomially many queries suffice in order to obtain an approximation ratio of 1 - 1 e . We consider a variation on this problem in which the value queries are required to be of uniform size: each queried set, like the desired solution itself, must contain k items. We show that polynomially many uniform size queries suffice in order to obtain an approximation ratio of 1 2 , and that an approximation ratio of 1 + ϵ 2 requires a number of queries that is exponential in ϵ k . For the interesting special case of coverage functions, we show that an approximation ratio strictly better than 1 2 is attainable with polynomially many uniform size queries. The “uniform size” requirement is motivated by situations in which a firm may offer a menu of exactly k items to its clients, where k is a parameter determined by external considerations. Performing a query corresponds to physically changing the identities of the items offered, and the reply to the query is deduced by observing the behavior of clients in response to the change. Queries that involve a number of items that differs from k may not be desirable due to these external considerations. In such situations it is natural to ask whether the same approximation ratios that can be guaranteed by general value queries can also be obtained by uniform size queries.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-016-0162-7