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
From MaRDI portal
Publication:3360178
DOI10.1137/0402008zbMath0733.05003OpenAlexW2140118062MaRDI QIDQ3360178
Publication date: 1989
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://research.tue.nl/nl/publications/on-the-size-of-systems-of-sets-every-t-of-which-have-an-sdr-with-an-application-to-the-worstcase-ratio-of-heuristics-for-packing-problems(beb57666-e367-401e-9183-513ee169eb06).html
worst-case ratiosubsetsSDRsystem of distinct representativesmaximum collection of pairwise disjoint sets
Related Items (80)
Looking at the stars ⋮ Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Hardness and approximation of traffic grooming ⋮ Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ Generalized Hypergraph Matching via Iterated Packing and Local Ratio ⋮ On spectrum sharing games ⋮ Complexity issues in color-preserving graph embeddings ⋮ Minimization of SONET ADMs in ring networks revisited ⋮ Dealing with several parameterized problems by random methods ⋮ Complexity results for rainbow matchings ⋮ An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ The limits of local search for weighted \(k\)-set packing ⋮ Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location ⋮ Local improvement algorithms for a path packing problem: a performance analysis based on linear programming ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Stochastic packing integer programs with few queries ⋮ Counting frequent patterns in large labeled graphs: a hypergraph-based approach ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ Uniform unweighted set cover: the power of non-oblivious local search ⋮ A 6/5-approximation algorithm for the maximum 3-cover problem ⋮ Approximating the directed path partition problem ⋮ Independent sets in Line of Sight networks ⋮ Approximability of sparse integer programs ⋮ Scheduling to minimize gaps and power consumption ⋮ On the maximum disjoint paths problem on edge-colored graphs ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Finding Large Independent Sets in Line of Sight Networks ⋮ Competitive router scheduling with structured data ⋮ Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Packing paths: recycling saves time ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ Two-dimensional packing with conflicts ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ Bin packing with fragmentable items: presentation and approximations ⋮ Algorithms for terminal Steiner trees ⋮ Approximating k-set cover and complementary graph coloring ⋮ Greedy matching: guarantees and limitations ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ Iterated local search with Trellis-neighborhood for the partial Latin square extension problem ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Shape rectangularization problems in intensity-modulated radiation therapy ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ 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 6/5-Approximation Algorithm for the Maximum 3-Cover Problem ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ Packing \(K_r\)s in bounded degree graphs ⋮ An improved kernelization for \(P_{2}\)-packing ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ Kernelization for edge triangle packing and covering via a discharging method ⋮ On cluster editing problem with clusters of small sizes ⋮ A deterministic approximation algorithm for metric triangle packing ⋮ A randomized approximation algorithm for metric triangle packing ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ A discharging method: improved kernels for edge triangle packing and covering ⋮ An improved approximation algorithm for metric triangle packing ⋮ The limits of local search for weighted \(k\)-set packing ⋮ The maximum 3-star packing problem in claw-free cubic graphs ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ Realization problems on reachability sequences ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Local search for the minimum label spanning tree problem with bounded color classes. ⋮ On approximating four covering and packing problems ⋮ Independent sets in bounded-degree hypergraphs ⋮ Weighted sum coloring in batch scheduling of conflicting jobs ⋮ Covering the edges of bipartite graphs using \(K_{2,2}\) graphs ⋮ Scheduling time-constrained multicast messages in circuit-switched tree networks. ⋮ Packing triangles in bounded degree graphs. ⋮ Distributed algorithms for matching in hypergraphs
This page was built for publication: 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
