Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
From MaRDI portal
Publication:6657247
DOI10.1016/J.DAM.2024.10.023MaRDI QIDQ6657247
Ilan Doron-Arad, Hadas Shachnai
Publication date: 6 January 2025
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
bipartite graphperfect graphmaximum independent sethardness of approximationbudgeted constrained maximization
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Budgeted matching and budgeted matroid intersection via the gasoline puzzle
- Approximation algorithms for time constrained scheduling
- Approximation of knapsack problems with conflict and forcing graphs
- A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- Tight Approximation Algorithms for Maximum Separable Assignment Problems
- Maximum Weighted Independent Sets with a Budget
- The Knapsack Problem with Conflict Graphs
- Approximation Schemes for Multi-Budgeted Independence Systems
- Approximation algorithms for NP-complete problems on planar graphs
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
- Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
- The Parameterized Complexity of k-B<scp>iclique</scp>
- Improved Approximation Algorithm for Two-Dimensional Bin Packing
- Parameterized Algorithms
- Approximating Bin Packing with Conflict Graphs via Maximization Techniques
- An EPTAS for budgeted matroid independent set
- An FPTAS for budgeted laminar matroid independent set
- An EPTAS for budgeted matching and budgeted matroid intersection via representative sets
This page was built for publication: Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6657247)
