A threshold of ln n for approximating set cover
From MaRDI portal
Publication:3158517
DOI10.1145/285055.285059zbMath1065.68573OpenAlexW2143996311WikidataQ56443116 ScholiaQ56443116MaRDI QIDQ3158517
No author found.
Publication date: 25 January 2005
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/285055.285059
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (only showing first 100 items - show all)
Towards optimal lower bounds for clique and chromatic number. ⋮ Inapproximability results for equations over finite groups ⋮ On the hardness of the minimum height decision tree problem ⋮ On domain-partitioning induction criteria: worst-case bounds for the worst-case based ⋮ Domination in some subclasses of bipartite graphs ⋮ A new approximation algorithm for \(k\)-set cover problem ⋮ Dynamic algorithms via the primal-dual method ⋮ Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks ⋮ Submodular learning and covering with response-dependent costs ⋮ Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks ⋮ Calculating approximation guarantees for partial set cover of pairs ⋮ Secluded connectivity problems ⋮ Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ Maximum coverage problem with group budget constraints ⋮ Multiple facility location on a network with linear reliability order of edges ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Min-energy broadcast in mobile ad hoc networks with restricted motion ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ Minimizing energies with hierarchical costs ⋮ The knapsack problem with neighbour constraints ⋮ Committee polyhedral separability: complexity and polynomial approximation ⋮ The probabilistic minimum dominating set problem ⋮ Spider covers and their applications ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Exponential inapproximability of selecting a maximum volume sub-matrix ⋮ Welfare maximization with friends-of-friends network externalities ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Maximum subset intersection ⋮ On the approximability of covering points by lines and related problems ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ An exact algorithm for the maximum leaf spanning tree problem. ⋮ A logarithmic approximation for polymatroid congestion games ⋮ On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints ⋮ Computing the arrangement of circles on a sphere, with applications in structural biology ⋮ On approximability of linear ordering and related NP-optimization problems on graphs. ⋮ Tight results on minimum entropy set cover ⋮ On the computational complexity of the minimum committee problem ⋮ A note on maximizing a submodular set function subject to a knapsack constraint ⋮ Hardness of optimal spaced seed design ⋮ Recommending links through influence maximization ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Counting the number of independent sets in chordal graphs ⋮ Designing cost-sharing methods for Bayesian games ⋮ On the complexity of minimizing interference in ad-hoc and sensor networks ⋮ Efficient sensor network design for continuous monitoring of moving objects ⋮ Computational study on a PTAS for planar dominating set problem ⋮ Rounding to an integral program ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Online dominating set ⋮ Complete partitions of graphs ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ Towards flexible demands in online leasing problems ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Complexity of distance paired-domination problem in graphs ⋮ On the approximability of Dodgson and Young elections ⋮ Approximability of clausal constraints ⋮ A note on line broadcast in digraphs under the edge-disjoint paths mode ⋮ Inapproximability results for equations over infinite groups ⋮ Algorithms for storage allocation based on client preferences ⋮ A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership ⋮ Improved approximation algorithms for capacitated facility location problems ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ Broadcast routing with minimum wavelength conversion in WDM optical networks ⋮ Exponential-time approximation of weighted set cover ⋮ Incremental deployment of network monitors based on Group Betweenness Centrality ⋮ Risk averse submodular utility maximization ⋮ Assortment optimization over time ⋮ Maximizing expected utility over a knapsack constraint ⋮ A constructive proof of swap local search worst-case instances for the maximum coverage problem ⋮ Semi-preemptive routing on trees ⋮ Lift-and-project methods for set cover and knapsack ⋮ Computational complexity of the minimum committee problem and related problems ⋮ Robust monotone submodular function maximization ⋮ Maximizing monotone submodular functions over the integer lattice ⋮ Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor ⋮ Path hitting in acyclic graphs ⋮ Red-blue covering problems and the consecutive ones property ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ On approximating four covering and packing problems ⋮ An application of the greedy heuristic of set cover to traffic checks ⋮ An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm ⋮ Independent sets in bounded-degree hypergraphs ⋮ A new approach for approximating node deletion problems ⋮ On approximation algorithms for the terminal Steiner tree problem ⋮ Hardness results and approximation algorithms of \(k\)-tuple domination in graphs ⋮ Hardness results and approximation algorithms for (weighted) paired-domination in graphs ⋮ Computational study on planar dominating set problem ⋮ Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis ⋮ Worst-case analysis of the greedy algorithm for a generalization of the maximum \(p\)-facility location problem ⋮ The labeled perfect matching in bipartite graphs ⋮ A note on submodular set cover on matroids ⋮ Steiner trees in uniformly quasi-bipartite graphs. ⋮ A note on the minimum label spanning tree. ⋮ On bounded occurrence constraint satisfaction ⋮ A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
This page was built for publication: A threshold of ln n for approximating set cover
