Published September 2024 | Version Published
Journal Article

Sparse graphical designs via linear programming

  • 1. ROR icon University of Michigan–Ann Arbor
  • 2. ROR icon California Institute of Technology
  • 3. ROR icon Georgia Institute of Technology

Abstract

Graphical designs are a framework for sampling and numerical integration of functions on graphs. In this note, we introduce a method to address the trade-off between graphical design sparsity and accuracy. We show how to obtain sparse graphical designs via linear programming and design objective functions that aim to maximize their accuracy. We showcase our approach using yellow taxicab data from New York City.

Copyright and License

© 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Acknowledgement

We thank the associate editor and anonymous referee for their suggestions, which improved our manuscript.

Funding

This material is based upon work supported by the National Science Foundation under Grant No. DMS-1929284 while the authors were in residence at the Institute for Computational and Experimental Research in Mathematics in Providence, RI, during the Discrete Optimization: Mathematics, Algorithms, and Computation semester program. The work of H. Al-Thani was made possible by the Graduate Sponsorship Research Award from the Qatar National Research Fund (a member of Qatar Foundation, grant number GSRA7-1-0419-20020). The findings herein reflect the work and are solely the responsibility of the authors. J. C. Martínez Mori was partially supported by NSF Grant No. 2144127, awarded to S. Samaranayake. J. C. Martínez Mori is supported by Schmidt Science Fellows, in partnership with the Rhodes Trust.

Contributions

Hessa Al-Thani: Writing – review & editing, Writing – original draft, Validation, Methodology, Investigation, Formal analysis, Conceptualization. Catherine Babecki: Writing – review & editing, Writing – original draft, Validation, Methodology, Investigation, Formal analysis, Conceptualization. J. Carlos Martínez Mori: Writing – review & editing, Writing – original draft, Visualization, Validation, Software, Methodology, Investigation, Formal analysis, Data curation, Conceptualization.

Additional details

Related works

Is new version of
Discussion Paper: arXiv:2309.00765 (arXiv)

Funding

National Science Foundation
DMS-1929284
Qatar National Research Fund
Qatar Foundation
GSRA7-1-0419-20020
National Science Foundation
CMMI-2144127
Schmidt Family Foundation
Rhodes Trust

Dates

Available
2024-07-18
Available Online
Accepted
2024-07-12
Accepted

Caltech Custom Metadata

Publication Status
Published