Approximation algorithms for NP-hard problems.
From MaRDI portal
Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Collections of articles of miscellaneous specific interest (00B15) Approximation algorithms (68W25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming (90-06)
Recommendations
Cited in
(only showing first 100 items - show all)- Object Caching for Queries and Updates
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Solving min ones 2-SAT as fast as vertex cover
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Scheduling equal length jobs with eligibility restrictions
- Towards optimal branching of linear and semidefinite relaxations for neural network robustness certification
- The generalized assignment problem with minimum quantities
- Fast distributed approximation for TAP and 2-edge-connectivity
- Graph spanners: a tutorial review
- On a posterior evaluation of a simple greedy method for set packing
- Approximating minimum feedback vertex sets in hypergraphs
- Optimal cuts and partitions in tree metrics in polynomial time
- Computing the asymptotic worst-case of bin packing lower bounds
- Intractability of assembly sequencing: unit disks in the plane
- A 1/2-approximation algorithm for maximum interval multi-cover
- Vehicle scheduling under the warehouse-on-wheels policy
- 2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem
- An APTAS for bin packing with clique-graph conflicts
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Minimum vertex cover in rectangle graphs
- Evolutionary local search for the edge-biconnectivity augmentation problem
- The hardness of placing street names in a Manhattan type map
- Complexity of majority monopoly and signed domination problems
- Competitive ratio of list scheduling on uniform machines and randomized heuristics
- Truthful mechanism design for multidimensional scheduling via cycle monotonicity
- Scheduling multicasts on unit-capacity trees and meshes.
- A lower bound for scheduling mechanisms
- Interactive and probabilistic proof-checking
- On the maximum edge-pair embedding bipartite matching
- An efficient fixed-parameter algorithm for 3-hitting set
- An improved mechanism for selfish bin packing
- A note on the minimum bounded edge-partition of a tree
- Design and performance evaluation of communication algorithms in multihop wireless networks with multiple channels
- A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM
- Hardness of optimal spaced seed design
- Geometric partitioning and robust ad-hoc network design
- scientific article; zbMATH DE number 1566497 (Why is no real title available?)
- On-line scheduling of parallel jobs with runtime restrictions
- Inapproximability of finding maximum hidden sets on polygons and terrains
- Mixing of the Glauber dynamics for the ferromagnetic Potts model
- An analysis of totally clairvoyant scheduling
- Fixed topology alignment with recombination
- A fast asymptotic approximation scheme for bin packing with rejection
- The Priority k-Median Problem
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
- On the Parameterized Complexity of the Expected Coverage Problem
- An approximation algorithm for scheduling two parallel machines with capacity constraints.
- AN OPTIMAL REBUILDING STRATEGY FOR AN INCREMENTAL TREE PROBLEM
- An improved approximation algorithm for vertex cover with hard capacities
- A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
- Scheduling orders for multiple product types with due date related objectives
- Simultaneous matchings: Hardness and approximation
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- On some optimization problems in molecular biology
- A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
- Drawing graphs by eigenvectors: theory and practice
- Complexity of core allocation for the bin packing game
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- The design of approximation algorithms
- Approximation algorithms for NP-hard problems
- APPLICATION PLACEMENT ON A CLUSTER OF SERVERS
- Approximation algorithms for Hamming clustering problems
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- On some network design problems with degree constraints
- Disruption recovery at airports: integer programming formulations and polynomial time algorithms
- Paired-domination problem on distance-hereditary graphs
- The complexity of probabilistic lobbying
- Approximation algorithm for the kinetic robust \(k\)-center problem
- Contemplations on Testing Graph Properties
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- On rectangular covering problems
- Efficient approximation algorithms for clustering point-sets
- An approximation algorithm for state minimization in 2-MDFAs
- Maximizing data locality in distributed systems
- Obtaining matrices with the consecutive ones property by row deletions
- Approximability of guarding weak visibility polygons
- PTAS for connected vertex cover in unit disk graphs
- Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
- Active influence spreading in social networks
- A new family of proximity graphs: class cover catch digraphs
- Pruning 2-connected graphs
- Online bin packing of squares and cubes
- On approximation of max-vertex-cover
- Randomness and computation
- Multiple voting location and single voting location on trees
- On approximability of linear ordering and related NP-optimization problems on graphs.
- Reroute sequence planning in telecommunication networks and compact vector summation.
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Primal-dual approximation algorithms for feedback problems in planar graphs
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- Variants of Euclidean k-center clusterings
- Colocating tasks in data centers using a side-effects performance model
- A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
- On k-connectivity problems with sharpened triangle inequality
- A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
This page was built for publication: Approximation algorithms for NP-hard problems.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3002852)
