On the ratio of optimal integral and fractional covers
From MaRDI portal
Publication:1224109
DOI10.1016/0012-365X(75)90058-8zbMath0323.05127OpenAlexW2163322487WikidataQ56391140 ScholiaQ56391140MaRDI QIDQ1224109
Publication date: 1975
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(75)90058-8
Related Items
A-priori upper bounds for the set covering problem, On pseudo-disk hypergraphs, A modified greedy heuristic for the set covering problem with improved worst case bound, Capacities: From information theory to extremal set theory, Improved performance of the greedy algorithm for partial cover, A theory for memory-based learning, Conditional covering: greedy heuristics and computational results, The probabilistic method yields deterministic parallel algorithms, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Cops and robbers in graphs with large girth and Cayley graphs, Near perfect coverings in graphs and hypergraphs, Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank, Codes with given distances, Weighted fractional and integral \(k\)-matching in hypergraphs, Upper bounds for \(\alpha \)-domination parameters, A comparison of two lower-bound methods for communication complexity, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, Optima of dual integer linear programs, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Towards the price of leasing online, Probabilistic construction of deterministic algorithms: approximating packing integer programs, New primal-dual algorithms for Steiner tree problems, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, Average stretch analysis of compact routing schemes, Pick-and-choose heuristics for partial set covering, Rounding algorithms for covering problems, Black-box Trace\&Revoke codes, Rainbow edge-coloring and rainbow domination, Identifying codes in vertex-transitive graphs and strongly regular graphs, On weighted covering numbers and the Levi-Hadwiger conjecture, 2-connected graphs with small 2-connected dominating sets., Approximating covering integer programs with multiplicity constraints, Approximation algorithms for a geometric set cover problem, On the approximability of covering points by lines and related problems, Uniform unweighted set cover: the power of non-oblivious local search, A unified approach to approximating partial covering problems, On the order of doubly transitive permutation groups, Construction of \(\epsilon\)-nets, Extremal problems, partition theorems, symmetric hypergraphs, Approximation algorithms for hitting objects with straight lines, Fast deterministic distributed algorithms for sparse spanners, On roman, global and restrained domination in graphs, \(k\)-domination and \(k\)-independence in graphs: A survey, Upper bounds on the balanced \(\langle \mathbf{r}, \mathbf{s} \rangle\)-domination number of a graph, Distributed algorithms for covering, packing and maximum weighted matching, The computational complexity and approximability of a series of geometric covering problems, A greedy partition lemma for directed domination, Complexity of the repeaters allocating problem, An upper bound of the number of tests in pooling designs for the error-tolerant complex model, Relative blocking sets of unions of Baer subplanes, Parallel and serial heuristics for the minimum set cover problem, Improved parallel approximation of a class of integer programming problems, Randomized approximation of bounded multicovering problems, The \(k\)-tuple domination number revisited, Write-isolated memories (WIMs), Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, The minimum substring cover problem, Processor optimization for flow graphs, Approximating source location and star survivable network problems, Weighted covering numbers of convex sets, The multicovering problem, Capacitated domination problem, Approximation algorithms for art gallery problems in polygons, A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership, On the geodetic and geodetic domination numbers of a graph, Min-sum bin packing, Covering compact metric spaces greedily, The ordered covering problem, Partial covering arrays: algorithms and asymptotics, Bounds for the covering number of a graph, Random constructions and density results, Hitting sets online and unique-MAX coloring, A randomised approximation algorithm for the hitting set problem, Minimum partition of an independence system into independent sets, Extended formulations, nonnegative factorizations, and randomized communication protocols, Linear programming bounds for codes via a covering argument, Path hitting in acyclic graphs, A note on two source location problems, A deterministic view of random sampling and its use in geometry, Approximation algorithms for scheduling unrelated parallel machines, Efficient approximation of Min Set Cover by moderately exponential algorithms, An application of the greedy heuristic of set cover to traffic checks, Connected domination of regular graphs, Approximating MAPs for belief networks is NP-hard and other theorems, On covering graphs by complete bipartite subgraphs, Independent sets in bounded-degree hypergraphs, Differential approximation algorithms for some combinatorial optimization problems, Zero knowledge and the chromatic number, The greedy algorithm for domination in graphs of maximum degree 3, On the hardness of approximating label-cover, Computational experience with approximation algorithms for the set covering problem, Weighted sum coloring in batch scheduling of conflicting jobs, Covering the edges of bipartite graphs using \(K_{2,2}\) graphs, Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis, A note on submodular set cover on matroids, Approximating the weight of shallow Steiner trees, On qualitatively independent partitions and related problems, Graph isomorphism problem, Good coverings of Hamming spaces with spheres, Randomized approximation for the set multicover problem in hypergraphs, Generalizations and strengthenings of Ryser's conjecture, Towards optimal lower bounds for clique and chromatic number., On a combinatorial framework for fault characterization, Sperner capacities, Improved approximation algorithms for minimum cost node-connectivity augmentation problems, Approximating subset \(k\)-connectivity problems, A new approximation algorithm for \(k\)-set cover problem, Intersection number and capacities of graphs, Upper bounds for the chromatic numbers of Euclidean spaces with forbidden Ramsey sets, Coverings and matchings in r-partite hypergraphs, Separation and approximation of polyhedral objects, A list heuristic for vertex cover, Almost optimal set covers in finite VC-dimension, On the limits of depth reduction at depth 3 over small finite fields, Approximating set multi-covers, Local ratio method on partial set multi-cover, On a theorem of Lovász on covers in \(r\)-partite hypergraphs, Randomized Online Algorithms for Set Cover Leasing Problems, Unrelated parallel machine scheduling with new criteria: complexity and models, Edge-covers in \(d\)-interval hypergraphs, A simple approximation algorithm for minimum weight partial connected set cover, Strengthening hash families and compressive sensing, The probabilistic minimum dominating set problem, Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl, Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs, Fair division with multiple pieces, Renaming and the weakest family of failure detectors, New pairwise spanners, Approximation algorithms and hardness results for labeled connectivity problems, New combinatorial structures with applications to efficient group testing with inhibitors, Approximation of the quadratic set covering problem, Approximating node-connectivity augmentation problems, Rigidity of proper colorings of \(\mathbb{Z}^d \), Saturating sets in projective planes and hypergraph covers, An extension of Stein-Lovász theorem and some of its applications, System of unbiased representatives for a collection of bicolorings, Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting), Asymptotic values of the Hall-ratio for graph powers, Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost, Approximating minimum cost source location problems with local vertex-connectivity demands, Algorithms for graphs with small octopus, Two sensitivity theorems in fuzzy integer programming., On upper bounds for multiple domination numbers of graphs, How to guard a graph against tree moves, Evaluation of reliability bounds by set covering models., On homomorphisms from the Hamming cube to \(\mathbb{Z}\), Hyperfinite graphings and combinatorial optimization, Sequential legislative lobbying, On approximation of the submodular set cover problem, Greedy domination on biclique-free graphs, Online budgeted maximum coverage, Asymptotic and constructive methods for covering perfect hash families and covering arrays, Towards flexible demands in online leasing problems, Covering problems in edge- and node-weighted graphs, Membership criteria and containments of powers of monomial ideals, Some new bounds for cover-free families through biclique covers, Fractionally total colouring \(G_{n,p}\), Restricted parameter range promise set cover problems are easy, Approximation algorithm for the partial set multi-cover problem, Covering radius in the Hamming permutation space, Information-theoretic approximations of the nonnegative rank, Intersection reverse sequences and geometric applications., On the differential approximation of MIN SET COVER, A modified greedy algorithm for dispersively weighted 3-set cover, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Conversion of coloring algorithms into maximum weight independent set algorithms, Reconstruction of Kauffman networks applying trees, Interval Packing and Covering in the Boolean Lattice, Approximation algorithm for the multicovering problem, Chromatic numbers of spheres, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, Lift-and-project methods for set cover and knapsack, Empirical study of the greedy heuristic as applied to the link selection problem, Covering graphs by monochromatic trees and Helly-type results for hypergraphs, On some covering problems in geometry, On the capacity of Boolean graph formulæ, Matchings and covers in hypergraphs, A primal-dual algorithm for the minimum partial set multi-cover problem, A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space, Approximating Source Location and Star Survivable Network Problems, On the rigidity of Vandermonde matrices, New probabilistic upper bounds on the domination number of a graph, Bounds for optimal coverings, Computing a small agreeable set of indivisible items, Landmarks in graphs, On interval and circular-arc covering problems, An analysis of the greedy algorithm for the submodular set covering problem, Generalized submodular cover problems and applications, Approximation algorithms for covering/packing integer programs, Approximating minimum cocolorings., Bounded queries, approximations, and the Boolean hierarchy, Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks, Local majorities, coalitions and monopolies in graphs: A review, Mining circuit lower bound proofs for meta-algorithms, On general frameworks and threshold functions for multiple domination, Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem., A fuzzy genetic algorithm for driver scheduling, Tight bounds on subexponential time approximation of set cover and related problems, Constant round distributed domination on graph classes with bounded expansion, A heuristic for cumulative vehicle routing using column generation, Minimal Subsidies in Expense Sharing Games, A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets, Small Stretch Pairwise Spanners and Approximate $D$-Preservers, Recent results in hardness of approximation, Point probe decision trees for geometric concept classes, An Improved Approximation Bound for Spanning Star Forest and Color Saving, Note on a problem of M. Talagrand, Partial Resampling to Approximate Covering Integer Programs, A comparison of two lower bound methods for communication complexity, Approximation algorithms for a genetic diagnostics problem, $$\epsilon $$-Almost Selectors and Their Applications, Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols, Approximability results for the $p$-centdian and the converse centdian problems, An Exact Method for the Minimum Feedback Arc Set Problem, Approximately counting independent sets in bipartite graphs via graph containers, Spanning trees with few non-leaves, Asymptotics of the chromatic number for quasi-line graphs, The Hardness of Approximating Poset Dimension, Detecting arrays for effects of single factors, Capacitated Domination and Covering: A Parameterized Perspective, Technical Note—Online Hypergraph Matching with Delays, A hybrid heuristic for the rectilinear picture compression problem, The localization game on oriented graphs, Independence numbers of Johnson-type graphs, Clustering in Hypergraphs to Minimize Average Edge Service Time, An approximation algorithm for 3-Colourability, Intersecting families of sets are typically trivial, Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs, Approximating minimum keys and optimal substructure screens, A broadcast key distribution scheme based on block designs, Unnamed Item, Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs, An efficient distributed algorithm for constructing small dominating sets, Capacitated Domination Problem, The Constant Inapproximability of the Parameterized Dominating Set Problem, Absolute bounds on optimal cost for a class of set covering problems, Set Covering with Ordered Replacement: Additive and Multiplicative Gaps, The Growth Constant of Odd Cutsets in High Dimensions, Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands, Approximating k-set cover and complementary graph coloring, On the metric dimension of incidence graph of M\"obius planes, Choosability with Separation of Complete Multipartite Graphs and Hypergraphs, On the Weisfeiler-Leman dimension of fractional packing, Small complete arcs in André planes of square order, Minimizing number of wavelengths in multicast routing trees in WDM networks, Sublinear Graph Approximation Algorithms, On Partial Covers, Reducts and Decision Rules, On a minimum linear classification problem, Unnamed Item, The Minimum Substring Cover Problem, Minimum Weighted Sum Bin Packing, Delta-systems and qualitative (in)dependence, On the primer selection problem in polymerase chain reaction experiments, Computing coverage kernels under restricted settings, Covering all points except one, Fractional path coloring in bounded degree trees with applications, Approximation algorithms for minimum weight partial connected set cover problem, An approximation algorithm for the partial vertex cover problem in hypergraphs, A Threshold Phenomenon for Random Independent Sets in the Discrete Hypercube, Constant-time distributed dominating set approximation, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP, On Geometric Set Cover for Orthants, Inapproximability of b-Matching in k-Uniform Hypergraphs, Multiple Domination, Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs, Distributed Dominating Set Approximations beyond Planar Graphs, Paths, Stars and the Number Three, On the Approximability of Some Haplotyping Problems, Lifting Theorems for Equality, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Small complete arcs in André planes of square order, Independent dominating sets in graphs of girth five, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, Distributed Spanner Approximation, Heuristics for the fixed cost median problem, On the Greedy Heuristic for Continuous Covering and Packing Problems, Unnamed Item, Superlinear Integrality Gaps for the Minimum Majority Problem, Worst case analysis of a class of set covering heuristics, Upper Bounds on the Size of Covering Arrays
Cites Work
- Unnamed Item
- Unnamed Item
- n-tuple colorings and associated graphs
- Normal hypergraphs and the perfect graph conjecture
- A Minimax Theorem for Directed Graphs
- Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
- On a Problem of C. E. Shannon in Graph Theory
- On a combinatorial problem. II
- Hide and Seek, Data Storage, and Entropy
- On a Problem of Additive Number Theory
