Intractability of assembly sequencing: Unit disks in the plane

DOI10.1007/3-540-63307-3_70zbMath1497.68528OpenAlexW2136320709MaRDI QIDQ5096948

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

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

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partitioning a planar assembly into two connected parts is NP-complete
• Translation separability of sets of polygons
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• Objects that cannot be taken apart with two hands
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The Approximability of Constraint Satisfaction Problems
• On Removing a Ball without Disturbing the Others
• Computing and Verifying Depth Orders
• Approximation algorithms for NP-complete problems on planar graphs
• Polynomially bounded minimization problems which are hard to approximate
• The Traveling Salesman Problem with Distances One and Two
• Scheduling Tasks with AND/OR Precedence Constraints

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