scientific article; zbMATH DE number 1256748
From MaRDI portal
Publication:4228484
zbMath0922.68067MaRDI QIDQ4228484
Publication date: 18 October 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Improved performance of the greedy algorithm for partial cover ⋮ Probabilistic proof systems — A survey ⋮ Unnamed Item ⋮ Service-constrained network design problems ⋮ Improved Approximation Algorithm for Fault-Tolerant Facility Placement ⋮ Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem ⋮ Construction of component tapes for radial placement machines ⋮ Greedy approximations for minimum submodular cover with submodular cost ⋮ On the connectivity preserving minimum cut problem ⋮ Computing Approximate Nash Equilibria in Network Congestion Games with Polynomially Decreasing Cost Functions ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ On the union of intermediate nodes of shortest paths ⋮ A derandomization using min-wise independent permutations ⋮ Optimizing cost flows by edge cost and capacity upgrade ⋮ Budget constrained minimum cost connected medians ⋮ An improved approximation scheme for the Group Steiner Problem ⋮ Local ratio method on partial set multi-cover ⋮ Self-improved gaps almost everywhere for the agnostic approximation of monomials ⋮ Approximation algorithms for the minimum power cover problem with submodular/linear penalties ⋮ Approximation algorithms for a genetic diagnostics problem ⋮ Intractability of assembly sequencing: Unit disks in the plane ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ On the difficulty of approximately maximizing agreements. ⋮ Approximating covering integer programs with multiplicity constraints ⋮ Approximation algorithms for a geometric set cover problem ⋮ Improved non-approximability results for vertex cover with density constraints ⋮ Relational data factorization ⋮ The Steiner connectivity problem ⋮ Wireless networking, dominating and packing ⋮ Complexity of minimum corridor guarding problems ⋮ Improving spanning trees by upgrading nodes ⋮ Improved non-approximability results for minimum vertex cover with density constraints ⋮ Integrated Supply Chain Management via Randomized Rounding ⋮ On the edge capacitated Steiner tree problem ⋮ Routing-efficient CDS construction in disk-containment graphs ⋮ Approximation schemes for deal splitting and covering integer programs with multiplicity constraints ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ On approximation of the submodular set cover problem ⋮ On the minimum monochromatic or multicolored subgraph partition problems ⋮ Preserving approximation in the min-weighted set cover problem ⋮ Minimum non-submodular cover problem with applications ⋮ Evaluation of monotone DNF formulas ⋮ Finding the maximal adversary structure from any given access structure ⋮ Upgrading bottleneck constrained forests ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ Combinatorial optimization algorithms for radio network planning ⋮ The complexity of base station positioning in cellular networks ⋮ Minimum monopoly in regular and tree graphs ⋮ Reload cost problems: Minimum diameter spanning tree ⋮ On Partial Covers, Reducts and Decision Rules ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ A primal-dual algorithm for the minimum partial set multi-cover problem ⋮ Modifying edges of a network to obtain short subgraphs ⋮ Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Class Steiner trees and VLSI-design ⋮ Center-based clustering under perturbation stability ⋮ A better constant-factor approximation for weighted dominating set in unit disk graph ⋮ Alarm placement in systems with fault propagation ⋮ Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs ⋮ On the limits of nonapproximability of lattice problems ⋮ Approximating the weight of shallow Steiner trees ⋮ Improving spanning trees by upgrading nodes ⋮ Clique is hard to approximate within \(n^{1-\epsilon}\) ⋮ Generalized submodular cover problems and applications ⋮ Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem ⋮ Improved methods for approximating node weighted Steiner trees and connected dominating sets. ⋮ On the flow cost lowering problem ⋮ A 2-approximation algorithm for the minimum weight edge dominating set problem ⋮ On approximability of the independent/connected edge dominating set problems ⋮ Approximation algorithms for terrain guarding. ⋮ Local majorities, coalitions and monopolies in graphs: A review ⋮ Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
