Design and analysis of approximation algorithms

DOI10.1007/978-1-4614-1701-9zbMATH Open1237.68009OpenAlexW603975761MaRDI QIDQ648055FDOQ648055

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

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

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)

Cited In (50)

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

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)