Design and analysis of approximation algorithms

DOI10.1007/978-1-4614-1701-9zbMath1237.68009OpenAlexW603975761MaRDI QIDQ648055

Ding-Zhu Du, Ker-I. Ko, Xiao-Dong Hu

Publication date: 22 November 2011

Published in: Springer Optimization and Its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4614-1701-9

zbMATH Keywords

partition linear programming semidefinite programming relaxation duality theory restriction approximation algorithms Steiner trees inapproximability greedy strategy guillotine cut

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Applications of mathematical programming (90C90) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Approximation algorithms (68W25)

Related Items (40)

Greedy approximation for the minimum connected dominating set with labeling ⋮ A short proof for stronger version of DS decomposition in set function optimization ⋮ A Branch-and-Cut Algorithm for Submodular Interdiction Games ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Maximum lifetime connected coverage with two active-phase sensors ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ A variation of DS decomposition in set function optimization ⋮ Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ On positive influence dominating sets in social networks ⋮ Approximation algorithm for (connected) Italian dominating function ⋮ Approximation for the minimum cost doubly resolving set problem ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network ⋮ On general threshold and general cascade models of social influence ⋮ Independent sets in Line of Sight networks ⋮ Greedy guarantees for non-submodular function maximization under independent system constraint with applications ⋮ Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Approximation algorithm for partial set multicover versus full set multicover ⋮ A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks ⋮ A novel approach for detecting multiple rumor sources in networks with partial observations ⋮ Minimum non-submodular cover problem with applications ⋮ On positive-influence target-domination ⋮ New approximations for Maximum Lifetime Coverage ⋮ A greedy algorithm for the fault-tolerant outer-connected dominating set problem ⋮ Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks ⋮ Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem ⋮ Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ Algorithms for randomized time-varying knapsack problems ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ SINGLE MACHINE DUE DATE ASSIGNMENT SCHEDULING PROBLEM WITH PRECEDENCE CONSTRAINTS AND CONTROLLABLE PROCESSING TIMES IN FUZZY ENVIRONMENT ⋮ Sensor Cover and Double Partition ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Time sensitive sweep coverage with minimum UAVs ⋮ Nearly tight approximation algorithm for (connected) Roman dominating set ⋮ Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem ⋮ Handling least privilege problem and role mining in RBAC

This page was built for publication: Design and analysis of approximation algorithms