scientific article; zbMATH DE number 1256748
From MaRDI portal
Publication:4228484
zbMATH Open0922.68067MaRDI QIDQ4228484FDOQ4228484
Authors: Uriel Feige 
Publication date: 18 October 1999
Title of this publication is not available (Why is that?)
Recommendations
Cited In (87)
- Optimal approximations made easy
- Finding the maximal adversary structure from any given access structure
- Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
- Title not available (Why is that?)
- On Partial Covers, Reducts and Decision Rules
- Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
- Local ratio method on partial set multi-cover
- Integrated Supply Chain Management via Randomized Rounding
- On the edge capacitated Steiner tree problem
- Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions
- Approximation algorithms for a genetic diagnostics problem
- Improved non-approximability results for vertex cover with density constraints
- Parallel algorithm for minimum partial dominating set in unit disk graph
- Deep approximation of set cover greedy algorithm for test set
- Approximating \(k\)-forest with resource augmentation: a primal-dual approach
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- Probabilistic proof systems -- a survey
- A primal-dual algorithm for the minimum partial set multi-cover problem
- Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem
- Pick, pack, \& survive: charging robots in a modern warehouse based on online connected dominating sets
- Intractability of assembly sequencing: unit disks in the plane
- Improved approximation algorithm for fault-tolerant facility placement
- Construction of component tapes for radial placement machines
- Approximating covering integer programs with multiplicity constraints
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- On the hardness of approximating minimization problems
- The projection games conjecture and the NP-hardness of \(\ln n\)-approximating Set-Cover
- A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership
- Upgrading bottleneck constrained forests
- On the connectivity preserving minimum cut problem
- Combinatorial optimization algorithms for radio network planning
- An improved approximation scheme for the Group Steiner Problem
- Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- \(O(n \log n)\) procedures for tightening cover inequalities
- A derandomization using min-wise independent permutations
- Approximating the weight of shallow Steiner trees
- Improved performance of the greedy algorithm for partial cover
- Modifying edges of a network to obtain short subgraphs
- Minimum monopoly in regular and tree graphs
- A threshold of ln n for approximating set cover
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Generalized submodular cover problems and applications
- Approximation algorithms for terrain guarding.
- Local majorities, coalitions and monopolies in graphs: A review
- Optimizing cost flows by edge cost and capacity upgrade
- On approximability of the independent/connected edge dominating set problems
- Algorithms for connected set cover problem and fault-tolerant connected set cover problem
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- Approximation algorithm for the partial set multi-cover problem
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- Budget constrained minimum cost connected medians
- On approximation of the submodular set cover problem
- Improving spanning trees by upgrading nodes
- Improving spanning trees by upgrading nodes
- Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
- On the flow cost lowering problem
- Complexity of minimum corridor guarding problems
- Class Steiner trees and VLSI-design
- Self-improved gaps almost everywhere for the agnostic approximation of monomials
- Minimum non-submodular cover problem with applications
- Greedy approximations for minimum submodular cover with submodular cost
- Center-based clustering under perturbation stability
- On the limits of nonapproximability of lattice problems
- On the minimum monochromatic or multicolored subgraph partition problems
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Approximation algorithms for a geometric set cover problem
- Approximation algorithms for the minimum power cover problem with submodular/linear penalties
- New and improved bounds for the minimum set cover problem
- An efficient distributed algorithm for constructing small dominating sets
- Improved non-approximability results for minimum vertex cover with density constraints
- On the union of intermediate nodes of shortest paths
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- Wireless networking, dominating and packing
- Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
- Reload cost problems: Minimum diameter spanning tree
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- Routing-efficient CDS construction in disk-containment graphs
- Relational data factorization
- The complexity of base station positioning in cellular networks
- On the difficulty of approximately maximizing agreements.
- Alarm placement in systems with fault propagation
- Service-constrained network design problems
- Title not available (Why is that?)
- Evaluation of monotone DNF formulas
- Preserving approximation in the min-weighted set cover problem
- The Steiner connectivity problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4228484)
