The limits of local search for weighted \(k\)-set packing

DOI10.1007/s10107-023-02026-3zbMATH Open1545.05036MaRDI QIDQ6589755

Meike Neuwohner

Publication date: 20 August 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

local searchindependent set\(d\)-claw free graphsweighted \(k\)-set packing

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of packing and covering (05B40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• The limits of local search for weighted \(k\)-set packing
• On the complexity of approximating \(k\)-set packing
• Greedy local improvement and weighted set packing approximation
• On local search for weighted \(k\)-set packing
• Approximating the $$k$$-Set Packing Problem by Local Improvements
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Color-coding
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Reducibility among Combinatorial Problems
• Large Neighborhood Local Search for the Maximum Set Packing Problem
• Maximum matching and a polyhedron with 0,1-vertices
• How to Sell Hyperedges: The Hypermatching Assignment Problem

This page was built for publication: The limits of local search for weighted \(k\)-set packing