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

DOI10.1137/0402008MaRDI QIDQ3360178zbMATH OpenOpenAlexFDO

Authors Cor Hurkens, Alexander Schrijver

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

zbMATH Keywords

maximum collection of pairwise disjoint setsSDRsubsetssystem of distinct representativesworst-case ratio

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Hypergraphs (05C65) Combinatorial optimization (90C27)

Recommendations

• On local search for weighted \(k\)-set packing
• On local search for weighted \(k\)-set packing
• On the number of SDR of a (t,n)-family
• scientific article; zbMATH DE number 4104975
• On disjointly representable sets

Cited in

(90)

• 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
• Fractional set systems with few disjoint pairs
• The maximum number of winning 2-sets
• A (3+)k-vertex kernel for edge-disjoint triangle packing
• Improved approximation algorithms for weighted 2-path partitions
• A local search algorithm for binary maximum 2-path partitioning
• Local search for the minimum label spanning tree problem with bounded color classes.
• Scheduling time-constrained multicast messages in circuit-switched tree networks.
• Packing triangles in bounded degree graphs.
• A 6/5-approximation algorithm for the maximum 3-cover problem
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• Distributed algorithms for matching in hypergraphs
• Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games
• The limits of local search for weighted \(k\)-set packing
• Stochastic packing integer programs with few queries
• Counting frequent patterns in large labeled graphs: a hypergraph-based approach
• Independent sets in Line of Sight networks
• The complexity of perfect matchings and packings in dense hypergraphs
• On spectrum sharing games
• Minimization of SONET ADMs in ring networks revisited
• Tight approximation bounds for combinatorial frugal coverage algorithms
• Scheduling to minimize gaps and power consumption
• Competitive router scheduling with structured data
• Packing paths: recycling saves time
• Algorithms for terminal Steiner trees
• Packing triangles in low degree graphs and indifference graphs
• Data dependent worst case bounds for weighted set packing
• An approximation algorithm for maximum triangle packing
• A modified greedy algorithm for dispersively weighted 3-set cover
• Dealing with several parameterized problems by random methods
• Complexity results for rainbow matchings
• 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
• Finding large independent sets in line of sight networks
• The complexity of perfect packings in dense graphs
• An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs
• Inapproximability of b-matching in k-uniform hypergraphs
• An Improved Approximation Bound for Spanning Star Forest and Color Saving
• Improved approximation algorithms for weighted 2-path partitions
• Generalized hypergraph matching via iterated packing and local ratio
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• On the maximum disjoint paths problem on edge-colored graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Improved algorithms for several parameterized problems based on random methods
• Approximating k-set cover and complementary graph coloring
• Combinatorics for smaller kernels: the differential of a graph
• Bin packing with fragmentable items: presentation and approximations
• Ignorance is almost bliss: near-optimal stochastic matching with few queries
• Greedy matching: guarantees and limitations
• Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
• Iterated local search with Trellis-neighborhood for the partial Latin square extension problem
• Shape rectangularization problems in intensity-modulated radiation therapy
• Approximation algorithms and hardness results for the clique packing problem
• Approximation algorithms and hardness results for the clique packing problem
• A randomized approximation algorithm for metric triangle packing
• On the Weisfeiler-Leman dimension of fractional packing
• Approximate multi-matroid intersection via iterative refinement
• Realization problems on reachability sequences
• The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
• Approximating the directed path partition problem
• Uniform unweighted set cover: the power of non-oblivious local search
• Approximability of sparse integer programs
• Packing K_rs in bounded degree graphs
• Kernelization for edge triangle packing and covering via a discharging method
• On cluster editing problem with clusters of small sizes
• The limits of local search for weighted k-set packing
• A deterministic approximation algorithm for metric triangle packing
• A discharging method: improved kernels for edge triangle packing and covering
• An improved approximation algorithm for metric triangle packing
• The maximum 3-star packing problem in claw-free cubic graphs
• Maximum common induced subforests and minimum common induced superforests of a set of forests
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Approximation algorithms for the k^+-star packing problem
• Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid
• A heuristic algorithm for rainbow matchings and its application in rainbow Ramsey number for matchings
• On linear and semidefinite programming relaxations for hypergraph matching
• An improved approximation algorithm for the maximum weight independent set problem in d-claw free graphs
• Maximum alternating clean balanced cycle decomposition and applications in rearrangement distance problems
• Semi-streaming algorithms for hypergraph matching
• Looking at the stars
• Hardness and approximation of traffic grooming
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Complexity issues in color-preserving graph embeddings
• Using fractional primal-dual to schedule split intervals with demands
• Two-dimensional packing with conflicts
• An improved kernelization for \(P_{2}\)-packing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3360178)