Optimization with uniform size queries

DOI10.1007/s00453-016-0162-7zbMath1386.90125OpenAlexW2413680293MaRDI QIDQ527424

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

submodular functioncoverage functionmaximizationconditional greedy algorithmvalue query

Mathematics Subject Classification ID

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

Related Items (1)

FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective

Cites Work

• Online maximum directed cut
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• The ellipsoid method and its consequences in combinatorial optimization
• Tight bound on Johnson's algorithm for maximum satisfiability
• Combinatorial auctions with decreasing marginal utilities
• Direct Sum Testing
• The Design of Approximation Algorithms
• Maximizing Non-monotone Submodular Functions
• A threshold of ln n for approximating set cover
• On the Computational Power of Demand Queries
• An analysis of approximations for maximizing submodular set functions—I
• Computing with Noisy Information
• 10.1162/153244303322753616
• On a combinatorial game

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