On Local Search for Weighted k-Set Packing

DOI10.1287/moor.23.3.640zbMath0977.90038OpenAlexW2089117840MaRDI QIDQ2757555

Esther M. Arkin, Refael Hassin

Publication date: 26 November 2001

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.23.3.640

zbMATH Keywords

local searchset packingperformance guarantee

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items (21)

Euclidean maximum matchings in the plane -- local to global ⋮ Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ On spectrum sharing games ⋮ The limits of local search for weighted \(k\)-set packing ⋮ Improved Parameterized Algorithms for Weighted 3-Set Packing ⋮ Angle Optimization in Target Tracking ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ Approximating the directed path partition problem ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Hardness of approximation for non-overlapping local alignments. ⋮ A 0.5358-approximation for Bandpass-2 ⋮ The path partition problem and related problems in bipartite graphs ⋮ On the bandpass problem ⋮ An approximation algorithm for maximum triangle packing ⋮ A modified greedy algorithm for dispersively weighted 3-set cover ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS ⋮ A randomized approximation algorithm for metric triangle packing ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ Local search for the minimum label spanning tree problem with bounded color classes.

This page was built for publication: On Local Search for Weighted k-Set Packing