Design and analysis of approximation algorithms
The book under review has been published as part of Springer's Optimization and Its Application series. It contains a large amount of precisely selected topics covering various aspects and design techniques related to approximation algorithms. It provides an intensive study of the main methods used in the field, with abundant applications following the discussion of each method. It is organized according to design methods instead of application problems. Thus, one can study approximation algorithms of the same nature together, and learn about the design techniques in a more unified way. It has been intended as a textbook for a graduate course in theoretical computer science. However, thanks to the rich set of results covered it can also be used as a reference book for postgraduate students and researchers in the area of design and analysis of algorithms. It also serves as a reference for established researchers by providing efficient tools for various applied areas like applied mathematics, engineering, medicine, economics, and other sciences. This book has grown out of lecture notes used by the authors at their universities. Besides being extremely useful to those who are interested in design and analysis techniques, graph connectivities, matroid optimization and submodular functions, the book is also of great interest to anyone interested in general combinatorial optimization theory. It is written in a highly scientific language and it is extraordinarily beneficial reading for graduates and researchers in mathematics and in theoretical computer science who focus on algorithms for solving optimization problems and also study applications involving such problems.
- On general threshold and general cascade models of social influence
- 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
- A greedy algorithm for the fault-tolerant outer-connected dominating set problem
- Approximation algorithms for the submodular edge cover problem with submodular penalties
- Algorithms and complexity for a class of combinatorial optimization problems with labelling
- 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
- An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
- A variation of DS decomposition in set function optimization
- Independent sets in Line of Sight networks
- Minimum non-submodular cover problem with applications
- Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks
- Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Handling least privilege problem and role mining in RBAC
- Maximum lifetime connected coverage with two active-phase sensors
- Approximation algorithm for the minimum weight connected k-subgraph cover problem
- Combinatorial approximation algorithms: a comparative review
- Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network
- Greedy guarantees for non-submodular function maximization under independent system constraint with applications
- scientific article; zbMATH DE number 1566497 (Why is no real title available?)
- Sensor cover and double partition
- Design, implementation, and analysis of maximum transversal algorithms
- The design of approximation algorithms
- Polynomial approximation
- In Memoriam: Ker-I Ko (1950–2018)
- scientific article; zbMATH DE number 4170925 (Why is no real title available?)
- A greedy algorithm for the fault-tolerant connected dominating set in a general graph
- scientific article; zbMATH DE number 1330032 (Why is no real title available?)
- 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
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
- Constant approximation for the lifetime scheduling problem of \(p\)-percent coverage
- 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
- New approximations for maximum lifetime coverage
- Approximation algorithms in combinatorial scientific computing
- On positive-influence target-domination
- Algorithms for randomized time-varying knapsack problems
- A greedy algorithm for the minimum 2-connected m-fold dominating set problem
- Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning
- Approximation algorithm for (connected) Italian dominating function
- Analyzing the 3-path vertex cover problem in planar bipartite graphs
- On positive influence dominating sets in social networks
- Greedy is good: constrained non-submodular function maximization via weak submodularity
- Total (restrained) domination in unit disk graphs
- PTAS for Euclidean travelling salesman problem with soft time windows
- An approximation algorithm for the prize-collecting connected dominating set problem
- Analyzing the 3-path vertex cover problem in selected graph classes
- On the inapproximability of two-machine open shop scheduling with exact delays
- Total (restrained) domination in B_k-EPG graphs and B_k-VPG graphs
- Greedy approximation for the minimum connected dominating set with labeling
- A short proof for stronger version of DS decomposition in set function optimization
- Approximation for the minimum cost doubly resolving set problem
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)
