Intractability of assembly sequencing: unit disks in the plane

DOI10.1007/3-540-63307-3_70MaRDI QIDQ5096948zbMATH OpenOpenAlexFDO

Authors Michael H. Goldwasser, Rajeev Motwani

Publication date 19 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63307-3_70

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Deterministic scheduling theory in operations research (90B35)

Recommendations

• On the complexity of assembly partitioning
• A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem
• Assembly sequences for polyhedra
• DISASSEMBLING TWO-DIMENSIONAL COMPOSITE PARTS VIA TRANSLATIONS
• A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM

Cites work

• Approximation algorithms for combinatorial problems
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for NP-hard problems.
• Computing and Verifying Depth Orders
• scientific article; zbMATH DE number 3945379 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1256750 (Why is no real title available?)
• scientific article; zbMATH DE number 871907 (Why is no real title available?)
• Objects that cannot be taken apart with two hands
• On Removing a Ball without Disturbing the Others
• Optimization, approximation, and complexity classes
• Partitioning a planar assembly into two connected parts is NP-complete
• Polynomially bounded minimization problems which are hard to approximate
• Scheduling Tasks with AND/OR Precedence Constraints
• The approximability of constraint satisfaction problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The Traveling Salesman Problem with Distances One and Two
• Translation separability of sets of polygons

Cited in

(5)

• On the hardness of approximating label-cover
• An efficient algorithm for searching implicit AND/OR graphs with cycles
• Precedence-Constrained Min Sum Set Cover
• Targeted least cardinality candidate key for relational databases
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems

This page was built for publication: Intractability of assembly sequencing: unit disks in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096948)