The Complexity of Partial Function Extension for Coverage Functions

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.30OpenAlexW2977488512MaRDI QIDQ5875484

Umang Bhaskar, Gunjan Kumar

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1907.07230

zbMATH Keywords

approximation algorithmPAC learningcoverage functionspartial function extension

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Is submodularity testable?
• Roofs and convexity
• Convex functions on non-convex domains
• Geometric algorithms and combinatorial optimization.
• Error-free and best-fit extensions of partially defined Boolean functions
• A non-extendibility certificate for submodularity and applications
• Combinatorial auctions with decreasing marginal utilities
• General truthfulness characterizations via convex analysis
• Recognizing Coverage Functions
• The Complexity Status of Problems Related to Sparsest Cuts
• Computational limitations on learning from examples
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Minimizing a Submodular Function on a Lattice
• The smallest convex extensions of a convex function
• The limitations of optimization from samples
• Extension of Convex Function
• Maximizing Social Influence in Nearly Optimal Time
• Learning submodular functions

This page was built for publication: The Complexity of Partial Function Extension for Coverage Functions