Intractability of assembly sequencing: Unit disks in the plane
From MaRDI portal
Publication:5096948
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
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