scientific article; zbMATH DE number 1330033
From MaRDI portal
Publication:4258216
zbMath0937.68002MaRDI QIDQ4258216
Giorgio Gambosi, Pierluigi Crescenzi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi, Giorgio Ausiello
Publication date: 1 September 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
approximate solutioncombinatorial optimization problemsprobabilistically checkable proofquality of approximationapproximability classes
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
On the uniform edge-partition of a tree, Robust regression via error tolerance, Complexity and approximation of the minimum recombinant haplotype configuration problem, A review on algorithms for maximum clique problems, Cooperation through social influence, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, The complexity of shelflisting, Fixed-parameter approximation: conceptual framework and approximability results, Note on maximal split-stable subgraphs, When the greedy algorithm fails, Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms, Genus characterizes the complexity of certain graph problems: Some tight results, Supermodular functions and the complexity of MAX CSP, A linear approximation method for the Shapley value, A survey on the linear ordering problem for weighted or unweighted tournaments, Resource constrained scheduling on multiple machines, Perfect Italian domination in graphs: complexity and algorithms, An algebraic proof of the real number PCP theorem, Genetic local search and hardness of approximation for the server load balancing problem, Unnamed Item, Zeros and approximations of holant polynomials on the complex plane, On the analysis of optimization problems in arc-dependent networks, A cooperative game-theoretic approach to the social ridesharing problem, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, The generalized definitions of the two-dimensional largest common substructure problems, Acyclic matching in some subclasses of graphs, Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences, CHAMP: a multipass algorithm for Max Sat based on saver variables, Domination and convexity problems in the target set selection model, Go-MOCE: greedy order method of conditional expectations for Max Sat, Algorithm and hardness results on neighborhood total domination in graphs, Job-shop scheduling in a body shop, Approximation algorithms for geometric conflict free covering problems, Intractability and approximation of optimization theories of cognition, Flip distance between triangulations of a planar point set is APX-hard, Global total \(k\)-domination: approximation and hardness results, Computing the differential of a graph: hardness, approximability and exact algorithms, The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?, On the complexity of constructing minimum changeover cost arborescences, Understanding planning with incomplete information and sensing, Crossing-constrained hierarchical drawings, An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem, Discrete optimization algorithms and problems of decision making in a fuzzy environment, Constrained sequence alignment: A general model and the hardness results, The path partition problem and related problems in bipartite graphs, Face-guarding polyhedra, Packing triangles in low degree graphs and indifference graphs, Rounding on the standard simplex: regular grids for global optimization, Compositional multiprocessor scheduling: the GMPR interface, Inapproximability results for the lateral gene transfer problem, On the complexity of the identifiable subgraph problem, Hardness results, approximation and exact algorithms for liar's domination problem in graphs, Reductions, completeness and the hardness of approximability, Finding minimum hidden guard sets in polygons --- tight approximability results, Controlling the losing probability in a monotone game, On the probabilistic minimum coloring and minimum \(k\)-coloring, The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Capacity inverse minimum cost flow problem, On the computational complexity of weighted voting games, Hedging uncertainty: approximation algorithms for stochastic optimization problems, Multiagent resource allocation in \(k\)-additive domains: preference representation and complexity, Minimum monopoly in regular and tree graphs, On the computational hardness based on linear fpt-reductions, On the complexity of the independent set problem in triangle graphs, The complexity of dissociation set problems in graphs, Completeness in approximation classes beyond APX, Inequity aversion pricing over social networks: approximation algorithms and hardness results, Algorithmic aspects of upper paired-domination in graphs, Algorithms of discrete optimization and their application to problems with fuzzy coefficients, Algorithmic aspects of upper edge domination, Approximation of the double traveling salesman problem with multiple stacks, Minimum 2-tuple dominating set of permutation graphs, On the complexity of the smallest grammar problem over fixed alphabets, The Stackelberg model in territorial planning, Algorithmic results on double Roman domination in graphs, Probabilistic characterization of random Max \(r\)-Sat, Analyzing unit read-once refutations in difference constraint systems, Complexity results on planar multifacility location problems with forbidden regions, Minimal distance of propositional models, Positive influence domination in graphs, The approximability of the weighted Hamiltonian path completion problem on a tree, Introduction to reconfiguration, A fully linear-time approximation algorithm for grammar-based compression, Comparing incomplete sequences via longest common subsequence, Upper bounds for the domination numbers of graphs using Turán's theorem and Lovász local lemma, Using the method of conditional expectations to supply an improved starting point for CCLS, Algorithm and hardness results on hop domination in graphs, The complexity of finding harmless individuals in social networks, Parameterized computation and complexity: a new approach dealing with NP-hardness, A combinatorial approach to the design of vaccines, Reprint of: Face-guarding polyhedra, Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs, On approximate learning by multi-layered feedforward circuits, On the typical case complexity of graph optimization, Lemmings is PSPACE-complete, On the complexity of the vector connectivity problem, A PCP of proximity for real algebraic polynomials, Robust weighted vertex \(p\)-center model considering uncertain data: an application to emergency management, Inferring local transition functions of discrete dynamical systems from observations of system behavior, Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring, On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality, The complexity of welfare maximization in congestion games, Identifying Codes in Hereditary Classes of Graphs and VC-Dimension, Algorithms with guarantee value for knapsack problems, Parameterized Complexity and Subexponential-Time Computability, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms, Integer Programming: Optimization and Evaluation Are Equivalent, Comparison of metaheuristics for the bilevel facility location and mill pricing problem, Known Algorithms for Edge Clique Cover are Probably Optimal, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Algorithmic Aspects of Disjunctive Domination in Graphs, Unnamed Item, A generic framework for approximation analysis of greedy algorithms for star bicoloring, Clique Cover and Graph Separation, Impact of soft ride time constraints on the complexity of scheduling in dial-a-ride problems, Unconstrained traveling tournament problem is APX-complete, Smoothed counting of 0–1 points in polyhedra, Matheuristics: survey and synthesis, Perfect forests in graphs and their extensions, Super-polynomial approximation branching algorithms, Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation, Comparison of models of planning public-private partnership, Complexity and Approximation Results for the Connected Vertex Cover Problem, Approximating Alternative Solutions, Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint, Unnamed Item, Dual parameterization and parameterized approximability of subset graph problems, Placement Inference for a Client-Server Calculus, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, Finding Large Independent Sets in Line of Sight Networks, Solving Graph Partitioning Problems with Parallel Metaheuristics, Fractals for Kernelization Lower Bounds, Solution to Motif Finding Problem in Membranes, When polynomial approximation meets exact computation, Algorithmic Aspects of the Maximum Colorful Arborescence Problem, Bounded Tree-Width and CSP-Related Problems, The Constant Inapproximability of the Parameterized Dominating Set Problem, Physical consequences of P≠NP and the density matrix renormalization group annealing conjecture, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Monitoring the edges of a graph using distances, On Some Geometric Problems of Color-Spanning Sets, Voting Procedures, Complexity of, An algorithm to compute integer ηth roots using subtractions, On minimum reload cost paths, tours, and flows, Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition, Deterministic Algorithms for Multi-criteria TSP, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, When polynomial approximation meets exact computation, Repetition-free longest common subsequence, Repetition-free longest common subsequence, Approximation algorithms and hardness results for the clique packing problem, Hardness results of global total \(k\)-domination problem in graphs, Trees in Graphs with Conflict Edges or Forbidden Transitions, The Next Whisky Bar, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Complexity and approximation ratio of semitotal domination in graphs, Unnamed Item, Approximability of unsplittable shortest path routing problems, On the Complexity Landscape of the Domination Chain, Inapproximability of finding maximum hidden sets on polygons and terrains, Fingerprint clustering with bounded number of missing values, Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs, As Close as It Gets, The strong domination problem in block graphs and proper interval graphs, Complexity and algorithms for semipaired domination in graphs, The temporal explorer who returns to the base, On the complexity of minimum maximal uniquely restricted matching, On the approximability of time disjoint walks, Unnamed Item, Experiments on the minimum linear arrangement problem, Bilevel Models for Investment Policy in Resource-Rich Regions, Optimal edge-coloring with edge rate constraints, P SYSTEMS WITH INPUT IN BINARY FORM, Quantum computation techniques for gauging reliability of interval and fuzzy data, The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$, Counting and enumeration complexity with application to multicriteria scheduling, On the tractability of covering a graph with 2-clubs, On a Three-Level Competitive Pricing Problem with Uniform and Mill Pricing Strategies, A Bilevel Competitive Location and Pricing Model with Nonuniform Split of Demand, Almost Transparent Short Proofs for NPℝ, Weighted counting of solutions to sparse systems of equations, Differential approximation of NP-hard problems with equal size feasible solutions, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Representing Utility Functions via Weighted Goals, Approximability of the Maximum Solution Problem for Certain Families of Algebras, Hitting times of local and global optima in genetic algorithms with very high selection pressure, Graphs and Algorithms in Communication Networks on Seven League Boots, Unnamed Item, Basic Terminology, Notation and Results, Introduction to the Maximum Solution Problem, Logic and Complexity in Cognitive Science, Vertex-Uncertainty in Graph-Problems, Packing Problems in Space Solved by CPLEX: An Experimental Analysis, Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems, Moderately exponential time and fixed parameter approximation algorithms, On complexity of the bilevel location and pricing problems, Primal-dual approximation algorithms for a packing-covering pair of problems, Theoretical complexity of grid cover problems used in radar applications, An approximability result of the multi-vehicle scheduling problem on a path with release and handling times, Parameterized complexity and approximation issues for the colorful components problems, Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, Multiple facility location on a network with linear reliability order of edges, Time traps in supply chains: is optimal still good enough?, Domination parameters with number 2: interrelations and algorithmic consequences, On inverse traveling salesman problems, Non-approximability of weighted multiple sequence alignment., Hardness of approximation for crossing number, Domination analysis of combinatorial optimization problems., Gathering of robots on meeting-points: feasibility and optimal resolution algorithms, Dynamic data resolution to improve the tractability of UMTS network planning, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT., Sparsification and subexponential approximation, Minimizing worst-case and average-case makespan over scenarios, Models and methods for solving the problem of network vulnerability, The complexity of secure domination problem in graphs, Channel assignment on graphs of bounded treewidth, Algorithms for graphs with small octopus, Solving the bilevel facility location problem under preferences by a Stackelberg-evolutionary algorithm, On approximability of linear ordering and related NP-optimization problems on graphs., Hardness of approximation for non-overlapping local alignments., Inapproximability and a polynomially solvable special case of a network improvement problem., Complexity of strict robust integer minimum cost flow problems: an overview and further results, Approximate inference in Bayesian networks: parameterized complexity results, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Algorithmic aspects of semitotal domination in graphs, Maximum disjoint paths on edge-colored graphs: approximability and tractability, Geometric hitting set for segments of few orientations, Partition into cliques for cubic graphs: Planar case, complexity and approximation, \(\varepsilon \)-optimization schemes and \(L\)-bit precision: alternative perspectives for solving combinatorial optimization problems, Tropical dominating sets in vertex-coloured graphs, Large independent sets in general random intersection graphs, On two extensions of equimatchable graphs, The 0-1 inverse maximum stable set problem, Domination problems with no conflicts, Improved algorithms and complexity results for power domination in graphs, Approximation hardness of dominating set problems in bounded degree graphs, The quadratic shortest path problem: complexity, approximability, and solution methods, Complexity of distance paired-domination problem in graphs, An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times, Efficient solutions for the far from most string problem, On the approximability of the simplified partial digest problem, Minimum dominating set of queens: a trivial programming exercise?, Data-independent neighborhood functions and strict local optima, Paired-domination problem on distance-hereditary graphs, Mathematical models for optimal usage of tributary cards in wavelength assignment for DWDM ring networks, Approximability of clausal constraints, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Optimal covering designs: complexity results and new bounds, Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Approximation algorithm for the partial set multi-cover problem, Playing monotone games to understand learning behaviors, On the differential approximation of MIN SET COVER, Learning local transductions is hard, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Hardness results and approximation algorithm for total liar's domination in graphs, Solution methods for the vertex variant of the network system vulnerability analysis problem, On the approximability of the maximum induced matching problem, The complexity of base station positioning in cellular networks, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, Designing optimally multiplexed SNP genotyping assays, The complexity of Boolean constraint satisfaction local search problems, Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?, Mean analysis of an online algorithm for the vertex cover problem, On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs, Precoloring extension of co-Meyniel graphs, Routing to reduce the cost of wavelength conversion, Algorithms for connected set cover problem and fault-tolerant connected set cover problem, Fast payment schemes for truthful mechanisms with verification, On the inapproximability of independent domination in \(2P_3\)-free perfect graphs, Computing small partial coverings, Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems, Approximation algorithms for multi-criteria traveling salesman problems, Red-blue covering problems and the consecutive ones property, Algorithms for compact letter displays: comparison and evaluation, The transportation problem with exclusionary side constraints, Approximability of minimum AND-circuits, Minimum weakly fundamental cycle bases are hard to find, Hardness of approximation for orthogonal rectangle packing and covering problems, Minimum-weight cycle covers and their approximability, Hardness results and approximation algorithms of \(k\)-tuple domination in graphs, The minimum likely column cover problem, Some APX-completeness results for cubic graphs, Hardness results and approximation algorithms for (weighted) paired-domination in graphs, \((r,p)\)-centroid problems on paths and trees, Improved parameterized set splitting algorithms: A Probabilistic approach, Non-approximability of weighted multiple sequence alignment for arbitrary metrics, A note on submodular set cover on matroids, Computational complexity in additive hedonic games, Packing triangles in bounded degree graphs., On the Hamming distance of constraint satisfaction problems., The inapproximability of non-NP-hard optimization problems., Logical analysis of data with decomposable structures., On bounded occurrence constraint satisfaction, 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, Differential approximation for optimal satisfiability and related problems, Looking at the stars, Flow shop non-idle scheduling and resource-constrained scheduling, A bilevel planning model for public-private partnership, Computing the permanent of (some) complex matrices, Sharp spectral bounds of several graph parameters using eigenvector norms, On the copy complexity of width 3 Horn constraint systems, Approximation algorithms for the TSP with sharpened triangle inequality, On the approximability of two tree drawing conventions, Concise finite-domain representations for PDDL planning tasks, Hard constraint satisfaction problems have hard gaps at location 1, Computational social choice for coordination in agent networks, An alternative approach for proving the NP-hardness of optimization problems, Online weighted flow time and deadline scheduling, Roman domination in subgraphs of grids, Approximating the minimal sensor selection for supervisory control, Strong computational lower bounds via parameterized complexity, Analyzing the complexity of finding good neighborhood functions for local search algorithms, Domination analysis for minimum multiprocessor scheduling, Approximation of min-max and min-max regret versions of some combinatorial optimization problems, On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]], Algorithmic aspects of open neighborhood location-domination in graphs, Models and complexity of multibin packing problems, Greedy-type resistance of combinatorial problems, Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover, Polynomial time approximation schemes and parameterized complexity, The maximum flow problem with disjunctive constraints, Parameterized complexity of \(k\)-anonymity: hardness and tractability, Longest common subsequence problem for unoriented and cyclic strings, Bound sets for biobjective combinatorial optimization problems, An efficient fixed-parameter algorithm for 3-hitting set, Differential approximation of MIN SAT, MAX SAT and related problems, Multiple voting location and single voting location on trees, Computing the minimum number of hybridization events for a consistent evolutionary history, Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights, Intractability and the use of heuristics in psychological explanations, Reoptimization of maximum weight induced hereditary subgraph problems, On the aggregation problem for synthesized web services, The \(l\)-diversity problem: tractability and approximability, Strong minimum energy \(2\)-hop rooted topology for hierarchical wireless sensor networks, The constrained shortest common supersequence problem, Flexible-attribute problems, Shortest path and maximum flow problems in networks with additive losses and gains, Composing medical crews with equity and efficiency, Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms, Data reductions and combinatorial bounds for improved approximation algorithms, On the approximability of the minimum strictly fundamental cycle basis problem, New results for the longest haplotype reconstruction problem, Repairing XML functional dependency violations, The transposition median problem is NP-complete, Routing multi-class traffic flows in the plane, An approximation scheme for the two-stage, two-dimensional knapsack problem, Extended formulation for CSP that is compact for instances of bounded treewidth, Optimizing end-to-end performance of data-intensive computing pipelines in heterogeneous network environments, Multi-criteria TSP: Min and Max combined, A framework for scalable greedy coloring on distributed-memory parallel computers, Mapping pipeline skeletons onto heterogeneous platforms, NP-completeness and APX-completeness of restrained domination in graphs, Paths, trees and matchings under disjunctive constraints, Joint task assignment and cache partitioning with cache locking for WCET minimization on MPSoC, Edge cover by connected bipartite subgraphs, On the inapproximability of maximum intersection problems, Algorithmic aspects of \(k\)-tuple total domination in graphs, Notes on inverse bin-packing problems, Graph clustering, A survey on the structure of approximation classes, On the complexity of core, kernel, and bargaining set, Bilevel competitive facility location and pricing problems, Partitioning a weighted partial order, The phasing of heterozygous traits: Algorithms and complexity, On the approximation of correlation clustering and consensus clustering, Approximating MAX SAT by moderately exponential and parameterized algorithms, Complexity of local search for the \(p\)-median problem, Approximation results for the weighted \(P_4\) partition problem, Approximability results for the maximum and minimum maximal induced matching problems, Bandwidth allocation in cellular networks with multiple interferences, Restricted and swap common superstring: a multivariate algorithmic perspective, Random shortest paths: non-Euclidean instances for metric optimization problems, Inapproximability results for graph convexity parameters, Bin packing with fragmentable items: presentation and approximations, On the max min vertex cover problem, Unrelated parallel machine scheduling -- perspectives and progress, Shortcutting directed and undirected networks with a degree constraint, Approximate counting for complex-weighted Boolean constraint satisfaction problems, On the complexity of the regenerator cost problem in general networks with traffic grooming, Structure of polynomial-time approximation, Anonymizing binary and small tables is hard to approximate, The full Steiner tree problem, Approximative solution methods for multiobjective combinatorial optimization. With discussion and a rejoinder by the authors., On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, Approximation algorithms for grooming in optical network design, Teaching randomized learners with feedback, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, The intractability of computing the Hamming distance, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Deterministic algorithms for multi-criteria max-TSP, Dense and sparse graph partition, Algorithmic aspects of \(b\)-disjunctive domination in graphs, Lower bounds for treewidth of product graphs, Binary linear programming solutions and non-approximability for control problems in voting systems, Algorithmic and hardness results for the colorful components problems, Minimum cost flow problem with conflicts, On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows, Covering edges in networks, Unique response Roman domination: complexity and algorithms, Obtaining approximately optimal and diverse solutions via dispersion, The multilevel facility location and pricing problems: the computational complexity and the stability analysis, On the complexity of minimum maximal acyclic matchings, Unit read-once refutations for systems of difference constraints, Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks, Linear Programming on the Stiefel Manifold, Unnamed Item, Hardness results of global Roman domination in graphs
