### Popularity Prediction for Social Media over Arbitrary Time Horizons

Daniel Haimovich, Dima Karamshuk, Thomas Leeper, Evgeniy Riabenko, Milan Vojnovic

International Symposium on Algorithms and Computation (ISAAC )

We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph *G = (V, E)* with positive edge weights *w* : *E→R*^{+} , and a non-increasing discount function *ƒ *(·) such that *ƒ *(1) = 1 and ƒ (*i*) = 0 for *i* > *k*, for some parameter *k* that is part of the problem definition. The problem is to sequence the vertices *V* so as to maximize ∑_{(u, v)∈E }ƒ(|d_{u} — d_{v }|) ⋅ *w *(*u, v *), where *d*_{v} ∈ {1, . . . , |V|} is the position of vertex *v* in the sequence.

We show that Ext-TSP is APX-hard to approximate in general and we give a (*k* + 1)- approximation algorithm for general graphs and a PTAS for some sparse graph classes such as planar or treewidth-bounded graphs.

Interestingly, the problem remains challenging even on very simple graph classes; indeed, there is no exact n^{o (k)} time algorithm for trees unless the ETH fails. We complement this negative result with an exact n^{O(k)} time algorithm for trees.

Daniel Haimovich, Dima Karamshuk, Thomas Leeper, Evgeniy Riabenko, Milan Vojnovic

Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga Behram, James Huang, Charles Bai, Michael Gschwind, Anurag Gupta, Myle Ott, Anastasia Melnikov, Salvatore Candido, David Brooks, Geeta Chauhan, Benjamin Lee, Hsien-Hsin S. Lee, Bugra Akyildiz, Max Balandat, Joe Spisak, Ravi Jain, Mike Rabbat, Kim Hazelwood

Liqi Yan, Qifan Wang, Yiming Cu, Fuli Feng, Xiaojun Quan, Xiangyu Zhang, Dongfang Liu