Physical Sciences and Mathematics Commons^™

Hypergraph Partitioning With Embeddings, Justin Sybrandt, Ruslan Shaydulin, Ilya Safro

Publications

The problem of placing circuits on a chip or distributing sparse matrix operations can be modeled as the hypergraph partitioning problem. A hypergraph is a generalization of the traditional graph wherein each "hyperedge" may connect any number of nodes. Hypergraph partitioning, therefore, is the NP-Hard problem of dividing nodes into k" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; font-size: 16px; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; color: rgb(93, 93, 93); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; position: relative;">kk similarly sized disjoint sets while …