Design and analysis of approximation algorithms

DOI10.1007/978-1-4614-1701-9MaRDI QIDQ648055zbMATH OpenOpenAlexFDO

Authors Du Ding-Zhu, Ker-I Ko, Xiaodong 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

linear programmingpartitionsemidefinite programmingapproximation algorithmsinapproximabilityrelaxationduality theoryrestrictionSteiner treesgreedy strategyguillotine cut

Mathematics Subject Classification ID

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

Recommendations

• The design of approximation algorithms
• Design and analysis of algorithms. A contemporary perspective
• Algorithm design: Foundations, analysis, and Internet examples
• Techniques for designing and analyzing algorithms
• Handbook of Approximation Algorithms and Metaheuristics

Cited in

(50)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• New approximations for maximum lifetime coverage
• Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage
• Greedy is good: constrained non-submodular function maximization via weak submodularity
• On general threshold and general cascade models of social influence
• Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks
• scientific article; zbMATH DE number 4170925 (Why is no real title available?)
• Greedy approximation for the minimum connected dominating set with labeling
• A short proof for stronger version of DS decomposition in set function optimization
• Single machine due date assignment scheduling problem with precedence constraints and controllable processing times in fuzzy environment
• Approximation algorithm for partial set multicover versus full set multicover
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Approximation algorithm for (connected) Italian dominating function
• Analyzing the 3-path vertex cover problem in planar bipartite graphs
• Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning
• Polynomial approximation
• Approximation algorithms for the submodular edge cover problem with submodular penalties
• Independent sets in Line of Sight networks
• Maximum lifetime connected coverage with two active-phase sensors
• Total (restrained) domination in unit disk graphs
• In Memoriam: Ker-I Ko (1950–2018)
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• Time sensitive sweep coverage with minimum UAVs
• Nearly tight approximation algorithm for (connected) Roman dominating set
• A Branch-and-Cut Algorithm for Submodular Interdiction Games
• A variation of DS decomposition in set function optimization
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Approximation for the minimum cost doubly resolving set problem
• Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem
• Approximation algorithms in combinatorial scientific computing
• On positive influence dominating sets in social networks
• scientific article; zbMATH DE number 1566497 (Why is no real title available?)
• Combinatorial approximation algorithms: a comparative review
• Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network
• The design of approximation algorithms
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
• On positive-influence target-domination
• Algorithms for randomized time-varying knapsack problems
• Design, implementation, and analysis of maximum transversal algorithms
• Minimum non-submodular cover problem with applications
• Approximation and optimization. Algorithms, complexity and applications. Based on the conference on approximation and optimization: algorithms, complexity, and applications, National and Kapodistrian University of Athens, Athens, Greece, June 29--30, 2017
• Handling least privilege problem and role mining in RBAC
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• Sensor cover and double partition
• 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
• Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• Algorithms and complexity for a class of combinatorial optimization problems with labelling

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q648055)