Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
type: Item
instance of: scholarly article
title: Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
author: Ilan Doron-Arad
author: Hadas Shachnai
published in: Discrete Applied Mathematics
publication date: 2025-01-06T00:00:00Z
Mathematics Subject Classification ID: 90Cxx
Mathematics Subject Classification ID: 05Cxx
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7962107
zbMATH Keywords: maximum independent set
zbMATH Keywords: budgeted constrained maximization
zbMATH Keywords: bipartite graph
zbMATH Keywords: perfect graph
zbMATH Keywords: hardness of approximation
MaRDI profile type: MaRDI publication profile
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Improved Approximation Algorithm for Two-Dimensional Bin Packing
cites work: Budgeted matching and budgeted matroid intersection via the gasoline puzzle
cites work: A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
cites work: Q5365101
cites work: A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
cites work: Parameterized Algorithms
cites work: An EPTAS for budgeted matching and budgeted matroid intersection via representative sets
cites work: An EPTAS for budgeted matroid independent set
cites work: An FPTAS for budgeted laminar matroid independent set
cites work: Approximating Bin Packing with Conflict Graphs via Maximization Techniques
cites work: Tight approximation algorithms for maximum separable assignment problems
cites work: Approximation Schemes for Multi-Budgeted Independence Systems
cites work: Q4400840
cites work: Approximation algorithms for time constrained scheduling
cites work: Maximum Weighted Independent Sets with a Budget
cites work: On Lagrangian relaxation for constrained maximization and reoptimization problems
cites work: The Parameterized Complexity of k-B<scp>iclique</scp>
cites work: Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
cites work: The Knapsack Problem with Conflict Graphs
cites work: Approximation of knapsack problems with conflict and forcing graphs
DOI: 10.1016/J.DAM.2024.10.023
description: scientific article; zbMATH DE number 7962107