« Unassigned Distance Geometry, Graph Rigidity and the Nanostructure Problem (tutorial)
Unassigned Distance Geometry, Graph Rigidity and the Nanostructure Problem (tutorial)
June 27, 2019, 9:00 AM - 10:20 AM
Location:
DIMACS Center
Rutgers University
CoRE Building
96 Frelinghuysen Road
Piscataway, NJ 08854
Click here for map.
Phillip Duxbury, Michigan State University
This talk will be a tutorial introduction to the unassigned variant (called uDG) of the DG problem, and how it arises in the problem of finding the atomic structure of materials. Two classes of optimization algorithm will be described, with both based on build-up methods but using dfferent strategies. Classes of problem for which the buildup methods are exact will be outlined and bounds on their computational time will be derived and tested using computational experiments. As in the DG problem, graph rigidity provides useful insights into the minimal number of distances that are required for there to be a unique solution to the uDG problem. A list of unsolved problems in the area will be discussed. Selected papers are listed below.
*This work was done in collaboration with co-authors of the papers listed below.
[1] P. Juhas, D. Cherba, P.M. Duxbury, W. Punch, S.J.L. Billinge, Ab-initio determination of solid state nanostructure, Nature 440, 655 (2006)
[2] P. Juhas, L. Granlund, P.M. Duxbury, W.F. Punch and S.J.L. Billinge, The LIGA algorithm for ab initio determination of nanostructure, Acta Crystallographica A64, 631- 640 (2008).
[3] S.R. Gujarathi, C.L. Farrow, C. Glosser, L. Granlund and P.M. Duxbury. Abinitio reconstruction of complex Euclidean networks in two dimensions. Phys. Rev. E89, number 53311, (2014).
[4] P.M. Duxbury, L. Granlund, S.R. Gujarathi, P. Juhas, S.J.L. Billinge. The unassigned distance geometry problem. Discrete Applied Mathematics 204, 117-132 (2016).
[5] S.J.L. Billinge, P.M. Duxbury, D.S. Goncalves, C. Lavor, A. Mucherino. Assigned and unassigned distance geometry: Applications to biological molecules and nanostructures. 4OR Quarterly Journal of Operations Research 14 (4), 337-376 (2016).
[6] S.J.L. Billinge, P.M. Duxbury, D.S. Goncalves, C. Lavor, A. Mucherino. Recent results on assigned and unassigned distance geometry: Applications to biological molecules and nanostructures. Annals of Operations Research 271 (1), 161-203 (2018)