General Information
| Student: | Corbet Elkins |
|---|---|
| Office: | CoRE 415 |
| School: | Purdue University |
| Contact: | ce383@rutgers.edu |
| Project: | Multi-Robot Path Planning: Structural Studies and High-Performance Algorithms |
| Mentor: | Jingjin Yu |
Project Description
Research Log
Week 1 (5/26-5/30)
Read through various proposed projects, ultimately deciding to work on the Rubiks Table problem. Tried several reductions to work towards the current goal. Worked on the initial presentation.
Current Goal: Prove minimizing parallel shuffles for the Rubiks Table problem is NP-hard.
Week 2 (6/2-6/6)
Continued working on showing NP-hardness of minimizing parallel shuffles. I believe I have a reduction after much trial and error.
Current Goal: Prove minimizing shuffles for the Rubiks table is NP-hard in the general setting.
Week 3 (6/9-6/13)
Finished the proof of NP-hardness of parallel Rubiks table shuffles.
Current Goal: Work towards showing minimizing shuffles for the Rubiks table is NP-hard.
Week 4 (6/16-6/20)
Got some minor results with regards to the Rubiks table problem. I started looking into some other related problems. One of which is a polyomino problem where we want to stack polyominoes such that we can always see at least one block from each.
Current Goal: Think about the polyomino problem
Week 5 (6/23-6/27)
Continued working on show NP-hardness of the Rubiks table problem. Read through this paper on NP-hardness of n x n x n Rubiks cube, which I think will be very helpful for proving NP-hardness of the labeled Rubiks table problem. I believe I have a reduction for showing the unlabeled Rubiks table is NP-hard, but the proof is still in the works.
Current Goal: Try to show NP-hardness of labeled Rubiks table and finish proof of hardness of regular Rubiks Table.
Week 6 (6/30-7/4)
Not much progress was made this week. I've still been working on proving hardness of the Rubik's table problem.