Max 2SAT-3, Net, Euclidea: Techniques and Results in Computational Inapproximability
This Master’s thesis investigates three diverse problem domains through the lens of computational inapproximability: Max 2SAT-3, the Net tile-rotating puzzle family, and the mobile game Euclidea. Max 2SAT-3 is a problem long known to be APX-complete, but finding a clear proof is harder than one migh...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156791 |