scientific article; zbMATH DE number 1330032

Publication date: 1 September 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

approximation algorithms combinatorial optimization problems quality of approximation LP-based algorithms

Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (84)

Computing Roman domatic number of graphs ⋮ A primer on the application of neural networks to covering array generation ⋮ A polynomial-time approximation scheme for the MAXSPACE advertisement problem ⋮ Set multi-covering via inclusion-exclusion ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ Sensor placement for fault location identification in water networks: a minimum test cover approach ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation ⋮ On the connectivity preserving minimum cut problem ⋮ Clustering on \(k\)-edge-colored graphs ⋮ A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering ⋮ Exact makespan minimization of unrelated parallel machines ⋮ Complete formulations of polytopes related to extensions of assignment matrices ⋮ A new asymptotic notation: Weak Theta ⋮ Counting Candy Crush configurations ⋮ Inapproximability results and bounds for the Helly and Radon numbers of a graph ⋮ A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times ⋮ A super-stabilizing \(\log(n)\)-approximation algorithm for dynamic Steiner trees ⋮ Runtime analysis of RLS and \((1 + 1)\) EA for the dynamic weighted vertex cover problem ⋮ Domination parameters with number 2: interrelations and algorithmic consequences ⋮ ``Grouping strategies and thresholding for high dimensional linear models: discussion ⋮ An improved algorithm for the \(L_2-L_p\) minimization problem ⋮ Quantifying spatial misallocation in centrally provided public goods ⋮ Approximability and efficient algorithms for constrained fixed-horizon POMDPs with durative actions ⋮ A variant of the Erdős–Rényi random graph process ⋮ Packing, partitioning, and covering symresacks ⋮ Steiner tree reoptimization in graphs with sharpened triangle inequality ⋮ Approximation of the quadratic knapsack problem ⋮ Justifying groups in multiwinner approval voting ⋮ IM2Vec: representation learning-based preference maximization in geo-social networks ⋮ Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton ⋮ Complexity of unconstrained \(L_2 - L_p\) minimization ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures ⋮ GMPLS label space minimization through hypergraph layouts ⋮ How to pack directed acyclic graphs into small blocks ⋮ On the approximability of some degree-constrained subgraph problems ⋮ Optimal facility location problem on polyhedral terrains using descending paths ⋮ On the inapproximability of maximum intersection problems ⋮ A graph-theoretic approach on optimizing informed-node selection in multi-agent tracking control ⋮ \(k\)-balanced center location problem: a new multi-objective facility location problem ⋮ Optimal wireless charger placement with individual energy requirement ⋮ Matching influence maximization in social networks ⋮ Stabbing Convex Polygons with a Segment or a Polygon ⋮ On the complexity of constructing minimum changeover cost arborescences ⋮ Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods ⋮ On scheduling multiple two-stage flowshops ⋮ Measuring the impact of MVC attack in large complex networks ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ Minimizing the number of max-power users in ad-hoc wireless networks with minimum node degree requirements ⋮ On a class of bilevel linear mixed-integer programs in adversarial settings ⋮ On the complexity of the regenerator cost problem in general networks with traffic grooming ⋮ A 2-approximation for the maximum satisfying bisection problem ⋮ Non-cooperative facility location and covering games ⋮ Temporal vertex cover with a sliding time window ⋮ Minimum vertex cover in rectangle graphs ⋮ Dynamic programming based algorithms for set multicover and multiset multicover problems ⋮ Rounding heuristics for multiple product dynamic lot-sizing in the presence of queueing behavior ⋮ Secure total domination in graphs: bounds and complexity ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Improved approximation algorithms for two-stage flowshops scheduling problem ⋮ Competitive Cost Sharing with Economies of Scale ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ Approximate algorithms for unrelated machine scheduling to minimize makespan ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ An improved approximation for maximum \(k\)-dependent set on bipartite graphs ⋮ Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Approximation algorithms in combinatorial scientific computing ⋮ Obtaining online approximation algorithms for facility dispersion from offline algorithms ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Sampling \(k\)-partite graphs with a given degree sequence ⋮ APX-hardness of domination problems in circle graphs ⋮ Gauges, loops, and polynomials for partition functions of graphical models ⋮ The complexity of finding harmless individuals in social networks ⋮ Approximate tradeoffs on weighted labeled matroids ⋮ Regret-minimizing Bayesian persuasion ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model ⋮ Unnamed Item ⋮ Balanced partitions of trees and applications

This page was built for publication: