Maximum bounded 3-dimensional matching is MAX SNP-complete
From MaRDI portal
Publication:922700
DOI10.1016/0020-0190(91)90246-EzbMath0711.68045OpenAlexW2071016718WikidataQ57255181 ScholiaQ57255181MaRDI QIDQ922700
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90246-e
Combinatorial optimization (90C27) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Approximation algorithms for NMR spectral peak assignment., Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games, The hardness of approximation: Gap location, APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD, Complexity of approximating bounded variants of optimization problems, Hardness and approximation results for packing Steiner trees, There is no asymptotic PTAS for two-dimensional vector packing, Hardness and approximation of traffic grooming, Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs, Improved Approximation Algorithms for Weighted 2-Path Partitions, Generalized Hypergraph Matching via Iterated Packing and Local Ratio, Polynomial time approximation schemes for class-constrained packing problems, On approximation properties of the Independent set problem for degree 3 graphs, Complexity issues in color-preserving graph embeddings, Matroid representation of clique complexes, Least and most colored bases, Computing envy-freeable allocations with limited subsidies, Partition into triangles on bounded degree graphs, Approximation and Nonapproximability for the One-Sided Scaffold Filling Problem, Tai mapping hierarchy for rooted labeled trees through common subforest, TRACTABLE AND INTRACTABLE VARIATIONS OF UNORDERED TREE EDIT DISTANCE, Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains, Approximation algorithms for clustering with dynamic points, Hardness of \(k\)-vertex-connected subgraph augmentation problem, Computing the minimum number of hybridization events for a consistent evolutionary history, The generalized definitions of the two-dimensional largest common substructure problems, Multi-shuttle crane scheduling in automated storage and retrieval systems, An improved kernel for planar vertex-disjoint triangle packing, On the approximability of the maximum common subgraph problem, Ascending-price mechanism for general multi-sided markets, Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture, Between a rock and a hard place: the two-to-one assignment problem, Shortest path and maximum flow problems in networks with additive losses and gains, Geometric Packing under Nonuniform Constraints, Cost-sharing games with rank-based utilities, Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs., The power of one evil secret agent, Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs, Unnamed Item, A 6/5-approximation algorithm for the maximum 3-cover problem, Independent sets in Line of Sight networks, Improved approximation algorithms for weighted 2-path partitions, Unnamed Item, Triangle strings: structures for augmentation of vertex-disjoint triangle sets, Computing the differential of a graph: hardness, approximability and exact algorithms, Partitioning a weighted partial order, Hardness and Approximation of Traffic Grooming, COLORING ALGORITHMS ON SUBCUBIC GRAPHS, The minimum feasible tileset problem, Scheduling games with machine-dependent priority lists, Bin packing with fragmentable items: presentation and approximations, Alignment of trees -- an alternative to tree edit, Distributed backup placement in networks, Strongly budget balanced auctions for multi-sided markets, Approximability of average completion time scheduling on unrelated machines, Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees, Completion of partial Latin hypercube designs: NP-completeness and inapproximability, Exact algorithms for the matrix bid auction, Inapproximability results for no-wait job shop scheduling., An approximation algorithm for maximum triangle packing, A \((1-1/e)\)-approximation algorithm for the generalized assignment problem, Order consolidation for batch processing, Conversion of coloring algorithms into maximum weight independent set algorithms, Designing optimally multiplexed SNP genotyping assays, On linear and semidefinite programming relaxations for hypergraph matching, MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS, A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem, Unnamed Item, Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive, A fixed-parameter-tractable algorithm for set packing, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, On the complexity of comparing evolutionary trees, A randomized approximation algorithm for metric triangle packing, Computational complexity characterization of protecting elections from bribery, Flexible allocation on related machines with assignment restrictions, Partition into Triangles on Bounded Degree Graphs, Unnamed Item, Generalized budgeted submodular set function maximization, An improved approximation algorithm for the minimum common integer partition problem, A genetic-based framework for solving (multi-criteria) weighted matching problems., Hardness of approximation for orthogonal rectangle packing and covering problems, On the approximability of the maximum agreement subtree and maximum compatible tree problems, An improved randomized approximation algorithm for maximum triangle packing, Some APX-completeness results for cubic graphs, Scalable Algorithms for Multiple Network Alignment, Multi-dimensional vector assignment problems, The hypergraph assignment problem, Packing triangles in bounded degree graphs., Finding disjoint paths in networks with star shared risk link groups, Approximability and parameterized complexity of multicover by \(c\)-intervals, Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems, Some MAX SNP-hard results concerning unordered labeled trees, Maximum bounded \(H\)-matching is Max SNP-complete, The generalized assignment problem with minimum quantities, Distributed algorithms for matching in hypergraphs
Cites Work
