The Ground-Set-Cost Budgeted Maximum Coverage Problem

Area of Science:

• Combinatorial Optimization
• Algorithm Design
• Computational Complexity

Background:

• The budgeted maximum coverage problem is a fundamental NP-hard problem with applications in various fields.
• A natural variant is introduced where vertex costs, rather than hyperedge costs, are considered within a budget constraint.
• This problem is motivated by applications in sponsored search auctions, specifically bid optimization.

Purpose of the Study:

• To investigate a novel variant of the budgeted maximum coverage problem with vertex costs.
• To develop efficient approximation algorithms for this problem.
• To analyze the approximability of the problem and identify conditions for exact or near-exact solutions.

Main Methods:

• The study employs techniques from approximation algorithms and complexity theory.
• Reductions from known hard problems like Densest k-Subgraph are used to establish inapproximability results.
• Specific algorithmic approaches are developed for different classes of hypergraphs, including greedy strategies and dynamic programming.

Main Results:

• The problem is shown to be at least as hard as the standard budgeted maximum coverage problem, implying [Formula: see text]-inapproximability.
• A [Formula: see text]-approximation algorithm is presented for general graphs.
• A fully polynomial-time approximation scheme (FPTAS) is derived for hypergraphs whose incidence graphs are forests (Berge-acyclic), with extensions for fixed feedback sets.
• A [Formula: see text]-approximation algorithm is provided for general hypergraphs based on maximum vertex degree.

Conclusions:

• The developed algorithms offer significant improvements for specific instances of the budgeted maximum coverage problem.
• The findings provide a theoretical understanding of the problem's complexity and its practical implications for bid optimization.
• Future work could explore further extensions and applications of these algorithmic techniques.