Optimization, approximation, and complexity classes

From MaRDI portal

Publication:1186548

Jump to:navigation, search

DOI10.1016/0022-0000(91)90023-XzbMath0765.68036WikidataQ89894956 ScholiaQ89894956MaRDI QIDQ1186548

Christos H. Papadimitriou, Mihalis Yannakakis

Publication date: 28 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

optimization approximability MAX NP MAX SNP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Methods for reconstructing the history of tandem repeats and their application to the human genome., Approximation algorithms for NMR spectral peak assignment., On the complexity of minimum \(q\)-domination partization problems, On the existence of subexponential parameterized algorithms, Approximation algorithm for MAX DICUT with given sizes of parts, Complexity of approximating bounded variants of optimization problems, Inapproximability results for equations over finite groups, Cluster graph modification problems, On decision and optimization (\(k\),\(l\))-graph sandwich problems, Complexity and approximation of the minimum recombinant haplotype configuration problem, Algorithmic results in secure total dominating sets on graphs, Logic minimization techniques with applications to cryptology, Fixed-parameter approximation: conceptual framework and approximability results, Approximability of identifying codes and locating-dominating codes, On constructing an optimal consensus clustering from multiple clusterings, On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint, On computational capabilities of Ising machines based on nonlinear oscillators, Supermodular functions and the complexity of MAX CSP, On the longest circuit in an alterable digraph, Tai mapping hierarchy for rooted labeled trees through common subforest, On approximability of optimization problems related to red/blue-split graphs, Asymptotically quasi-optimal cryptography, Normal forms for second-order logic over finite structures, and classification of NP optimization problems, The complexity of optimal design of temporally connected graphs, Approximation algorithms for tree alignment with a given phylogeny, Large cuts with local algorithms on triangle-free graphs, A class of spectral bounds for max \(k\)-cut, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, The generalized definitions of the two-dimensional largest common substructure problems, FPGA implementation of a stochastic neural network for monotonic pseudo-Boolean optimization, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Independent sets in Line of Sight networks, Algorithm and hardness results on neighborhood total domination in graphs, On the complexity of computing the temporal hybridization number for two phylogenies, On defensive alliances and strong global offensive alliances, Donation center location problem, Maximal strip recovery problem with gaps: hardness and approximation algorithms, Greed is good for deterministic scale-free networks, PCPs and the hardness of generating synthetic data, Flip distance between triangulations of a planar point set is APX-hard, Max NP-completeness made easy, Improved non-approximability results for minimum vertex cover with density constraints, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), Computing the differential of a graph: hardness, approximability and exact algorithms, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, Network design with a discrete set of traffic matrices, A branch-and-bound algorithm for solving max-\(k\)-cut problem, On the geometric red-blue set cover problem, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, Solving the optimum communication spanning tree problem, Minimization of decision trees is hard to approximate, Minimum vertex cover in ball graphs through local search, Hardness results, approximation and exact algorithms for liar's domination problem in graphs, An approximation of the minimum vertex cover in a graph, On some tractable and hard instances for partial incentives and target set selection, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks, Order consolidation for batch processing, Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation, On the approximability of the maximum induced matching problem, Conversion of coloring algorithms into maximum weight independent set algorithms, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, On the maximum independent set problem in subclasses of subcubic graphs, The optimal statistical median of a convex set of arrays, The ferry cover problem, On the complexity of finding emerging patterns, Minimizing the number of switch instances on a flexible machine in polynomial time, Smooth and strong PCPs, Algorithmic aspects of upper paired-domination in graphs, Algorithmic aspects of upper edge domination, Producing genomic sequences after genome scaffolding with ambiguous paths: complexity, approximation and lower bounds, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Metabolic networks are NP-hard to reconstruct, \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel, Submodular unsplittable flow on trees, Approximability of open \(k\)-monopoly problems, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Algorithmic aspects of Roman domination in graphs, Double vertex-edge domination in graphs: complexity and algorithms, Local search for the minimum label spanning tree problem with bounded color classes., Minimum fill-in: inapproximability and almost tight lower bounds, Assortment planning for multiple chain stores, On the complexity of the approximation of nonplanarity parameters for cubic graphs, Positive influence domination in graphs, Bicriteria streaming algorithms to balance gain and cost with cardinality constraint, Parameterized complexity of multi-node hubs, Derandomized graph products, A note on the satisfactory partition problem: constant size requirement, Algorithm and hardness results on hop domination in graphs, The complexity of finding harmless individuals in social networks, On the terminal Steiner tree problem., On the Hamming distance of constraint satisfaction problems., Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs, Classical symmetries and the quantum approximate optimization algorithm, On weighted vs unweighted versions of combinatorial optimization problems, The nonapproximability of OBDD minimization, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., On subexponential and FPT-time inapproximability, The maximum clique problem in multiple interval graphs, Differential approximation for optimal satisfiability and related problems, On the Complexity of Finding a Potential Community, Unnamed Item, On Finding Small 2-Generating Sets, The Maximum k-Colorable Subgraph Problem and Related Problems, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, On the approximability of some maximum spanning tree problems, Graph layout problems, Intractability of assembly sequencing: Unit disks in the plane, Algorithmic aspects of small quasi-kernels, On the computational complexity of Roman\(\{2\}\)-domination in grid graphs, Algorithms for maximizing monotone submodular function minus modular function under noise, MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems, Quantum Annealing versus Digital Computing, An Exact Method for the Minimum Feedback Arc Set Problem, On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows, On log-time alternating Turing machines of alternation depth k, Structure in approximation classes, The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, On parallel versus sequential approximation, On the kernel and related problems in interval digraphs, Exact algorithms and hardness results for geometric red-blue hitting set problem, Non-oblivious local search for graph and hypergraph coloring problems, A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, Algorithmic results on locating-total domination in graphs, Algorithmic results in Roman dominating functions on graphs, Unnamed Item, On the complexity of minimum maximal acyclic matchings, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Complexity of maximum cut on interval graphs, Online and Approximate Network Construction from Bounded Connectivity Constraints, Algorithmic and complexity aspects of problems related to total restrained domination for graphs, Priority-based bin packing with subset constraints, Fully dynamic maintenance of vertex cover, Approximating minimum keys and optimal substructure screens, Improved non-approximability results for vertex cover with density constraints, The complexity of spanning tree problems involving graphical indices, Maximum Cut Parameterized by Crossing Number, Unnamed Item, Unnamed Item, Max-independent set and the quantum alternating operator ansatz, Some notes on the nearest neighbour interchange distance, When polynomial approximation meets exact computation, New Valid Inequalities for the Optimal Communication Spanning Tree Problem, Grothendieck’s Theorem, past and present, On the Approximability of Comparing Genomes with Duplicates, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, When polynomial approximation meets exact computation, Metafinite model theory, MNP: A class of NP optimization problems, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Repetition-free longest common subsequence, Algorithmic aspects of total Roman ${2}$-domination in graphs, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Repetition-free longest common subsequence, On Maximum Edge Cuts of Connected Digraphs, The complexity of multiple sequence alignment with SP-score that is a metric, MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, The Minimum Substring Cover Problem, Maximizing agreements with one-sided error with applications to heuristic learning, Hardness and methods to solve CLIQUE, On the complexity of comparing evolutionary trees, Cardinality of relations and relational approximation algorithms, Maximizing agreements with one-sided error with applications to heuristic learning, On the complexity of the minimum outer-connected dominating set problem in graphs, The temporal explorer who returns to the base, On the complexity of minimum maximal uniquely restricted matching, Order Scheduling Models: Hardness and Algorithms, Lower bounds for the happy coloring problems, Approximability of covering cells with line segments, Near optimal multiple alignment within a band in polynomial time, Unnamed Item, Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs, A Logical Approach to Constraint Satisfaction, Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph, Linear game non-contextuality and Bell inequalities—a graph-theoretic approach, Unnamed Item, Algorithmic complexity of weakly connected Roman domination in graphs, Stackelberg Max Closure with Multiple Followers, On the ordered list subgraph embedding problems, Algorithmic aspects of total Roman and total double Roman domination in graphs, Orienting graphs to optimize reachability, The NPO-completeness of the longest Hamiltonian cycle problem, Approximate Max \(k\)-Cut with subgraph guarantee, Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}, A natural family of optimization problems with arbitrarily small approximation thresholds, Hard constraint satisfaction problems have hard gaps at location 1, Tractability-preserving transformations of global cost functions, Complexity issues in color-preserving graph embeddings, Complexity of approximating CSP with balance/hard constraints, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, On the longest common rigid subsequence problem, Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem, Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks, Strong computational lower bounds via parameterized complexity, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Finding disjoint paths with related path costs, Analyzing the complexity of finding good neighborhood functions for local search algorithms, A nonmonotone GRASP, A network flow approach to the minimum common integer partition problem, Graph editing to a fixed target, Using fractional primal-dual to schedule split intervals with demands, Exact algorithms and applications for tree-like Weighted Set Cover, Polynomial time approximation schemes and parameterized complexity, The maximum flow problem with disjunctive constraints, Combined super-/substring and super-/subsequence problems, On the complexity of deriving position specific score matrices from positive and negative sequences, The longest common subsequence problem for arc-annotated sequences, Differential approximation of MIN SAT, MAX SAT and related problems, Power optimization for connectivity problems, Computing the minimum number of hybridization events for a consistent evolutionary history, Approximability of the vertex cover problem in power-law graphs, A note on anti-coordination and social interactions, Subjective-cost policy routing, The multi-multiway cut problem, Lagrangean bounds for the optimum communication spanning tree problem, Exact algorithms and APX-hardness results for geometric packing and covering problems, Revisiting the minimum breakpoint linearization problem, Separator-based data reduction for signed graph balancing, Parameterized and subexponential-time complexity of satisfiability problems and applications, Complexity of majority monopoly and signed domination problems, Max-leaves spanning tree is APX-hard for cubic graphs, The Stackelberg minimum spanning tree game, A randomized PTAS for the minimum consensus clustering with a fixed number of clusters, On the approximability and hardness of minimum topic connected overlay and its special instances, Uniform unweighted set cover: the power of non-oblivious local search, Computing bond orders in molecule graphs, The locomotive fleet fueling problem, NP-completeness and APX-completeness of restrained domination in graphs, On the approximability of some degree-constrained subgraph problems, The traveling salesman problem with flexible coloring, Derandomized parallel repetition via structured PCPs, Online maximum directed cut, On scheduling \textsc{DAGs} for volatile computing platforms: area-maximizing schedules, Algorithmic aspects of \(k\)-tuple total domination in graphs, On the algorithmic effectiveness of digraph decompositions and complexity measures, A survey on the structure of approximation classes, Reoptimization of max \(k\)-cover: approximation ratio threshold, Practical algorithms for MSO model-checking on tree-decomposable graphs, Approximation algorithms for intersection graphs, Independent dominating set problem revisited, The computational complexity and approximability of a series of geometric covering problems, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, Approximating \(k\)-generalized connectivity via collapsing HSTs, On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion, A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach, A note on the clustered set covering problem, Approximate solution of NP optimization problems, On input read-modes of alternating Turing machines, A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, Local search, reducibility and approximability of NP-optimization problems, Alignment of trees -- an alternative to tree edit, The interval constrained 3-coloring problem, Complexities of efficient solutions of rectilinear polygon cover problems, Unrelated parallel machine scheduling -- perspectives and progress, Approximating Max NAE-\(k\)-SAT by anonymous local search, Primal-dual approximation algorithms for integral flow and multicut in trees, Randomized approximation of bounded multicovering problems, Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, On robust clusters of minimum cardinality in networks, A note on the descriptive complexity of maximization problems, Optimization problems in multiple subtree graphs, Structure of polynomial-time approximation, Complexity issues in vertex-colored graph pattern matching, Pseudo-Boolean optimization, The full Steiner tree problem, Approximation algorithms for grooming in optical network design, Inapproximability of maximal strip recovery, Complexity and approximation of the constrained forest problem, Minimal multicut and maximal integer multiflow: a survey, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, On the hardness of finding near-optimal multicuts in directed acyclic graphs, Clustering with lower-bounded sizes. A general graph-theoretic framework, Schedules for marketing products with negative externalities, There is no EPTAS for two-dimensional knapsack, Approximability of scheduling problems with resource consuming jobs, Combinatorial PCPs with short proofs, Oracle computations in parallel numerical linear algebra, The complexity of minimizing and learning OBDDs and FBDDs, The hardness of approximation: Gap location, Approximations for the maximum acyclic subgraph problem, Approximability and hardness of geometric hitting set with axis-parallel rectangles, A short note on the approximability of the maximum leaves spanning tree problem, On the power of multi-prover interactive protocols, Probabilistically checkable proofs and their consequences for approximation algorithms, Approximability of maximum splitting of k-sets and some other Apx-complete problems, On approximation algorithms for the minimum satisfiability problem, On an approximation measure founded on the links between optimization and polynomial approximation theory, New local search approximation techniques for maximum generalized satisfiability problems, Inferring a tree from walks, The hardness of approximate optima in lattices, codes, and systems of linear equations, On fixed-parameter tractability and approximability of NP optimization problems, Computational study of valid inequalities for the maximum \(k\)-cut problem, The complexity and approximability of finding maximum feasible subsystems of linear relations, MNP: A class of NP optimization problems, Rounding algorithms for covering problems, Metafinite model theory, Efficient delay routing, On the complexity of computing MP distance between binary phylogenetic trees, On the approximability of some Maximum Spanning Tree Problems, On the complexity of the shortest-path broadcast problem, Complexity of total outer-connected domination problem in graphs, Non-approximability of weighted multiple sequence alignment., The task allocation problem with constant communication., Sparsification and subexponential approximation, The many facets of upper domination, The complexity of secure domination problem in graphs, Complexity and lowers bounds for power edge set problem, Restricted assignment scheduling with resource constraints, Affine reductions for LPs and SDPs, Local approximations for maximum partial subgraph problem., On approximability of linear ordering and related NP-optimization problems on graphs., Hardness of approximation for non-overlapping local alignments., Distinguishing string selection problems., Differential approximation results for the Steiner tree problem, Limitations of semidefinite programs for separable states and entangled games, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, Finding a potential community in networks, Finding a most parsimonious or likely tree in a network with respect to an alignment, Deciding the existence of a cherry-picking sequence is hard on two trees, On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Approximation algorithms for connected graph factors of minimum weight, Partition into cliques for cubic graphs: Planar case, complexity and approximation, The 0-1 inverse maximum stable set problem, Competitive algorithms for multistage online scheduling, The minimum substring cover problem, Maximizing business value by optimal assignment of jobs to resources in grid computing, Commitment under uncertainty: Two-stage stochastic matching problems, On unrooted and root-uncertain variants of several well-known phylogenetic network problems, Complexity of distance paired-domination problem in graphs, An improved lower bound on approximation algorithms for the closest substring problem, The transitive minimum Manhattan subnetwork problem in 3 dimensions, An updated survey on the linear ordering problem for weighted or unweighted tournaments, The approximability of non-Boolean satisfiability problems and restricted integer programming, A mixed integer linear programming formulation of the maximum betweenness problem, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Approximability of partitioning graphs with supply and demand, Parameterizing above or below guaranteed values, Routing to reduce the cost of wavelength conversion, Finding occurrences of protein complexes in protein-protein interaction graphs, Red-blue covering problems and the consecutive ones property, A unified approximation algorithm for node-deletion problems, On a scheduling problem of time deteriorating jobs, Connected domination of regular graphs, Alphabet indexing for approximating features of symbols, On the approximation of protein threading, Vertex and edge covers with clustering properties: Complexity and algorithms, On the hardness of allocating frequencies for hybrid networks, A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses, Integer programming as a framework for optimization and approximability, Class Steiner trees and VLSI-design, Paintshop, odd cycles and necklace splitting, Computational experience with approximation algorithms for the set covering problem, Some APX-completeness results for cubic graphs, On the approximability of the Steiner tree problem in phylogeny, Hardness results and approximation algorithms for (weighted) paired-domination in graphs, Cryptography with constant input locality, Counting problems over the reals, PTAS for connected vertex cover in unit disk graphs, Covering the edges of bipartite graphs using \(K_{2,2}\) graphs, Priority algorithms for graph optimization problems, Non-approximability of weighted multiple sequence alignment for arbitrary metrics, Interactive and probabilistic proof-checking, The labeled perfect matching in bipartite graphs, Approximating minimum feedback vertex sets in hypergraphs, Clique is hard to approximate within \(n^{1-\epsilon}\), Structural properties of bounded relations with an application to NP optimization problems, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, The computational complexity of some problems of linear algebra, A 2-approximation algorithm for the minimum weight edge dominating set problem, Hardness results for neural network approximation problems, Which problems have strongly exponential complexity?, A randomized approximation scheme for metric MAX-CUT, Some MAX SNP-hard results concerning unordered labeled trees, Computing similarity between RNA structures, On bounded occurrence constraint satisfaction, Maximum bounded \(H\)-matching is Max SNP-complete, Approximation of the Clustered Set Covering Problem, Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, Acyclic Matching in Some Subclasses of Graphs, APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD, Safe Approximation and Its Relation to Kernelization, Grothendieck-Type Inequalities in Combinatorial Optimization, Complexity and Polynomially Solvable Special Cases of QUBO, Local Search to Approximate Max NAE-$$k$$-Sat Tightly, Improved approximations of independent sets in bounded-degree graphs, Recent results in hardness of approximation, Some recent strong inapproximability results, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, On approximation properties of the Independent set problem for degree 3 graphs, Approximation of Constraint Satisfaction via local search, The Birth and Early Years of Parameterized Complexity, Parameterized Complexity and Subexponential-Time Computability, Complexity results for rainbow matchings, Approximating a class of combinatorial problems with rational objective function, Online Admission Control and Embedding of Service Chains, Genus characterizes the complexity of certain graph problems: Some tight results, A survey on the linear ordering problem for weighted or unweighted tournaments, Polynomial approximation: a structural and operational study. (Abstract of thesis), Algorithmic Aspect of Minus Domination on Small-Degree Graphs, TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE, Unnamed Item, Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions, Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximationa, NP-completeness: A retrospective, A primal-dual approach to approximation of node-deletion problems for matroidal properties, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, Computational study of a branching algorithm for the maximum \(k\)-cut problem, On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE, Super-polynomial approximation branching algorithms, Acyclic matching in some subclasses of graphs, Approximability results for the converse connectedp-centre problem^†, On the complexity of variations of mixed domination on graphs^†, Approximating Alternative Solutions, Probabilistic CEGAR, Probabilistic nonunitary gate in imaginary time evolution, On the approximation hardness of geodetic set and its variants, The Approximability of Partial Vertex Covers in Trees, A semidefinite relaxation based global algorithm for two-level graph partition problem, Local Monotonicity in Probabilistic Networks, Unnamed Item, The approximation of maximum subgraph problems, Polynomially bounded minimization problems which are hard to approximate, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, On the approximation of shortest common supersequences and longest common subsequences, Multiway cuts in directed and node weighted graphs, On the hardness of range assignment problems, atalog: A logic language for expressing search and optimization problems, Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, Parameterized Complexity of Multi-Node Hubs, How to Cut a Graph into Many Pieces, Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees, Restricted Common Superstring and Restricted Common Supersequence, Proving completeness by logic, Inapproximability results for the lateral gene transfer problem, Linear time algorithms for generalized edge dominating set problems, A tutorial on the cross-entropy method, Reductions, completeness and the hardness of approximability, Independent set of intersection graphs of convex objects in 2D, A simple filter-and-fan approach to the facility location problem, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Complexity results on restricted instances of a paint shop problem for words, A modified greedy algorithm for dispersively weighted 3-set cover, Complexity and approximation ratio of semitotal domination in graphs, Minimum monopoly in regular and tree graphs, On the computational hardness based on linear fpt-reductions, On maximum planar induced subgraphs, A class of node based bottleneck improvement problems, Completeness in approximation classes beyond APX, Generalized \(k\)-multiway cut problems, On the Complexity Landscape of the Domination Chain, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, Cost Minimisation in Multi-interface Networks, A note on the complexity of minimum latency data aggregation scheduling with uniform power in physical interference model, Deterministic and randomized polynomial‐time approximation of radii, Optimal deterministic auctions with correlated priors, On Geometric Set Cover for Orthants, Approximation Algorithms for Minimum Chain Vertex Deletion, Definable Inapproximability: New Challenges for Duplicator, Upper Domination: Complexity and Approximation, Maximum Motif Problem in Vertex-Colored Graphs, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, On Approximating an Implicit Cover Problem in Biology, Learning Hurdles for Sleeping Experts, Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks, On the Maximum Uniquely Restricted Matching for Bipartite Graphs, Approximation of a batch consolidation problem, The approximability of the weighted Hamiltonian path completion problem on a tree, Tight lower bounds for certain parameterized NP-hard problems, On Dinur’s proof of the PCP theorem, Parameterized computation and complexity: a new approach dealing with NP-hardness, A \(2^{|E|/4}\)-time algorithm for MAX-CUT, ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS, On approximate learning by multi-layered feedforward circuits, Moderately exponential time and fixed parameter approximation algorithms, Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap, Algorithmic aspects of total Roman {3}-domination in graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1186548&oldid=12051693"