Optimization with uniform size queries

DOI10.1007/S00453-016-0162-7MaRDI QIDQ527424zbMATH OpenOpenAlexFDO

Authors Moshe Tennenholtz, Uriel Feige

Publication date 11 May 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-016-0162-7

zbMATH Keywords

conditional greedy algorithmcoverage functionmaximizationsubmodular functionvalue query

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Let \(f\) be a nonnegative, monotone, submodular set function over an \(n\)-element set \(U\). A \textit{value query} to \(f\) is a set \(S \subseteq U\) and its \textit{reply} is the value \(f(S)\). The authors study the following computational problem: given a positive integer \(k\) and \(f\) as above which can only be accessed using value queries of size \(k\), output a set \(S \subseteq U\) of size \(k\) that maximizes \(f(S)\). The authors show that polynomially many such queries are sufficient to obtain an approximation ratio of 1/2, and that an approximation ratio of \((1+\varepsilon)/2\) requires a number of queries that is exponential in \(\varepsilon k\). For the special case of \textit{coverage functions}, it is shown that an approximation ratio strictly better than 1/2 is attainable with polynomially many queries of size \(k\).

Recommendations

• Maximizing Non-monotone Submodular Functions
• scientific article; zbMATH DE number 7051222
• Fast algorithms for maximizing submodular functions
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• Fast algorithms for maximizing monotone nonsubmodular functions

Cites work

• 10.1162/153244303322753616
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Combinatorial auctions with decreasing marginal utilities
• Computing with Noisy Information
• Direct sum testing (extended abstract)
• Maximizing Non-monotone Submodular Functions
• On a combinatorial game
• On the computational power of demand queries
• Online maximum directed cut
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The design of approximation algorithms
• The ellipsoid method and its consequences in combinatorial optimization
• Tight bound on Johnson's algorithm for maximum satisfiability

Cited in

(5)

• Testing coverage functions
• Recognizing coverage functions
• Optimal sample cost residues for differential database batch query problems
• The power of an example: hidden set size approximation using group queries and conditional sampling
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective

This page was built for publication: Optimization with uniform size queries

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