Approximation algorithms for NP-hard problems.
From MaRDI portal
Collections of articles of miscellaneous specific interest (00B15) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming (90-06) Approximation methods and heuristics in mathematical programming (90C59)
Recommendations
Cited in
(only showing first 100 items - show all)- On k-connectivity problems with sharpened triangle inequality
- Approximating the maximum clique minor and some subgraph homeomorphism problems
- A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
- Approximation algorithms for a hierarchically structured bin packing problem
- A lower bound for scheduling mechanisms
- PTAS for connected vertex cover in unit disk graphs
- APX-hardness of domination problems in circle graphs
- New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- On approximation algorithms for the minimum satisfiability problem
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- Scheduling multicasts on unit-capacity trees and meshes.
- An approximation algorithm for scheduling two parallel machines with capacity constraints.
- On approximability of linear ordering and related NP-optimization problems on graphs.
- Reroute sequence planning in telecommunication networks and compact vector summation.
- On the algebraic complexity of some families of coloured Tutte polynomials
- On the minimum label spanning tree problem
- Interactive and probabilistic proof-checking
- Approximating minimum feedback vertex sets in hypergraphs
- Fixed topology alignment with recombination
- Linear time-approximation algorithms for bin packing
- On-line scheduling revisited
- Evolutionary local search for the edge-biconnectivity augmentation problem
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
- The hardness of placing street names in a Manhattan type map
- Approximation algorithms for constructing specific subgraphs with minimum number of length-bounded stock pieces
- The complexity of probabilistic lobbying
- Dynamic bin packing with unit fraction items revisited
- Total variation discrepancy of deterministic random walks for ergodic Markov chains
- Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
- Bin packing under linear constraints
- Maximum coverage problem with group budget constraints
- Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities
- An approximation algorithm for soft capacitated k-facility location problem
- LP-relaxations for tree augmentation
- A theory and algorithms for combinatorial reoptimization
- Active influence spreading in social networks
- Disruption recovery at airports: integer programming formulations and polynomial time algorithms
- Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes
- Colocating tasks in data centers using a side-effects performance model
- Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
- A cutting plane approach for integrated planning and scheduling
- Measuring instance difficulty for combinatorial optimization problems
- Exponential penalty function control of loss networks
- The approximability of non-Boolean satisfiability problems and restricted integer programming
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Core instances for testing: a case study
- Batched bin packing
- On complexity of unconstrained hyperbolic 0--1 programming problems
- Regret in the on-line decision problem
- Strong lower bounds for the prize collecting Steiner problem in graphs
- On approximation of max-vertex-cover
- A reduction technique for weighted grouping problems
- Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
- Maximum subset intersection
- Greedy -approximation algorithm for covering with arbitrary constraints and submodular cost
- A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
- Fast distributed approximation for TAP and 2-edge-connectivity
- Paired-domination problem on distance-hereditary graphs
- Selfish colorful bin packing games
- Graph spanners: a tutorial review
- Complete-subgraph-transversal-sets problem on bounded treewidth graphs
- A hybrid evolutionary algorithm for the offline Bin Packing Problem
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses
- Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
- Approximation algorithms for constructing required subgraphs using stock pieces of fixed length
- Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- 2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem
- The polygon burning problem
- Discrete dynamical system approaches for Boolean polynomial optimization
- A landscape-based analysis of fixed temperature and simulated annealing
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- Scheduling jobs with sizes and delivery times on identical parallel batch machines
- The community structure of human cellular signaling network
- Approximation algorithms for constructing some required structures in digraphs
- The freight consolidation and containerization problem
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Dynamic programming optimization in line of sight networks
- Scheduling equal length jobs with eligibility restrictions
- Efficient approximation algorithms for maximum coverage with group budget constraints
- Obtaining matrices with the consecutive ones property by row deletions
- Approximating the optimal sequence of acquisitions and sales with a capped budget
- Offline black and white bin packing
- Approximability of guarding weak visibility polygons
- Direct routing: Algorithms and complexity
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- Dynamic bin packing of unit fractions items
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Maximizing the guarded boundary of an Art Gallery is APX-complete
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
- Approximation and online algorithms for multidimensional bin packing: a survey
- An approximation algorithm for the dynamic facility location problem with outliers
- A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
- Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
- Approximation of the quadratic set covering problem
- Pruning 2-connected graphs
- A competitive analysis for balanced transactional memory workloads
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
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)
