The Complexity of Partial Function Extension for Coverage Functions

DOI10.4230/LIPICS.APPROX-RANDOM.2019.30MaRDI QIDQ5875484zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• A non-extendibility certificate for submodularity and applications
• Combinatorial auctions with decreasing marginal utilities
• Computational limitations on learning from examples
• Convex functions on non-convex domains
• Error-free and best-fit extensions of partially defined Boolean functions
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Extension of convex function
• Geometric algorithms and combinatorial optimization.
• Is submodularity testable?
• Learning submodular functions
• Maximizing social influence in nearly optimal time
• Minimizing a Submodular Function on a Lattice
• Recognizing Coverage Functions
• Roofs and convexity
• Sketching valuation functions
• The complexity status of problems related to sparsest cuts
• The limitations of optimization from samples
• The smallest convex extensions of a convex function

Cited in

(2)

• scientific article; zbMATH DE number 7765404 (Why is no real title available?)
• Positivity and convexity in incomplete cooperative games

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

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