Program

Proceedings (direct link, no subscription required)



August 3 (Thursday)


7:45–8:45 Registration

8:45–10:00

Jiannong Cao, Openning(Chair: Yixin Cao)
Dániel Marx, The optimality program for parameterized algorithms


10:00–10:30 COFFEE & TEA BREAK


10:30–12:10

SESSION 1 (Chair: Dániel Marx)


Jakub Gajarský, Petr Hlineny, Martin Koutecky, and Shmuel Onn
Parameterized shifted combinatorial optimization

Qilong Feng, Senmin Zhu, and Jianxin Wang
An improved kernel for parameterized bisection above tight lower bound

Pranabendu Misra, Fahad Panolan, Ramanujan M. S., and Saket Saurabh
Linear representation of transversal matroids and gammoids parameterized by rank

Hoang-Oanh Le and Van Bang Le
NP-hardness and structural results for half-squares of tree convex bipartite graphs

SESSION 2 (Chair: Daming Zhu)


Yuval Filmus, Hamed Hatami, Yaqiao Li, and Suzin You
Information complexity of the and function in the two-party and multi-party settings

Kun He, Qian Li, and Xiaoming Sun
A tighter relation between sensitivity complexity and certificate complexity

Purnata Ghosal, Om Prakash, and Raghavendra Rao B V
On constant depth circuits parameterized by degree: identity testing and depth reduction

Akinori Kawachi, Kenichi Kawano, Francois Le Gall, and Suguru Tamaki
Quantum query complexity of unitary operator discrimination


12:10–14:00 Lunch break


14:00–15:40

SESSION 3 (Chair: Xiaoming Sun)


Zhi-Zhong Chen, Guohui Lin, Lusheng Wang, Yong Chen, and Dan Wang
Approximation algorithms for the maximum weight internal spanning tree problem

Yiyao Jiang
Constant approximation for stochastic orienteering problem with $(1+\epsilon)$-budget relaxation

Guangwei Wu and Jianxin Wang
Approximation algorithms for scheduling multiple two-stage flowshops

Dongmei Zhang, Chunlin Hao, Chenchen Wu, Dachuan Xu, and Zhenning Zhang
A local search approximation algorithm for the $k$-means problem with penalties

SESSION 4 (Chair: Gill Barequet)


Elena Khramtcova and Evanthia Papadopoulou
Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended

Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung, and Ralf Klasing
The approximability of the p-hub center problem with parameterized triangle inequality

Pradeesha Ashok, Aniket Basu Roy, and Sathish Govindarajan
Local search strikes again: PTAS for variants of geometric covering and packing

Hee-Kap Ahn, Nicola Baraldo, Eunjin Oh, and Francesco Silvestri
A time-space trade-off for triangulations of points in the plane


15:40–16:10 Coffee & Tea break


16:10–17:50

SESSION 5(Chair: Yota Otachi)


Mikko Koivisto, Petteri Laakkonen, and Juho Lauri
NP-completeness results for partitioning a graph into total dominating sets

Congsong Zhang and Yong Gao
On the complexity of k-metric antidimension problem and the size of k-antireloving sets in random graphs

Alan Carneiro, Fabio Protti, and Uéverton Souza
Deletion graph problems based on deadlock resolution

SESSION 6 (Chair: Hsu-Chun Yen)


Stanley Fung
Optimal online two-way trading with bounded number of transactions

Ruta Mehta and Vijay Vazirani
An incentive compatible, efficient market for air traffic flow management

Maximilian Drees, Matthias Feldotto, Sören Riechers, and Alexander Skopalik
Pure Nash equilibria in restricted budget games

Zhou Chen, Yukun Cheng, Qi Qi, and Xiang Yan
Incentive ratios of a proportional sharing mechanism in resource sharing


18:00–18:30 Business meeting


August 4 (Friday)


9:00–10:00

Shang-Hua Teng, Scalable algorithms for data and network analysis(Chair: Jiannong Cao)


10:00–10:30 COFFEE & TEA BREAK


10:30–12:10

SESSION 7 (Chair: Akinori Kawachi)


Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno and Kunihiro Wasa
Efficient enumeration of maximal $k$-degenerate subgraphs in a chordal graph

Qian Li and Xiaoming Sun
On the modulo degree complexity of Boolean functions

Gill Barequet, Mira Shalah and Yufei Zheng
An improved lower bound on the growth constant of polyiamonds

Panagiotis Charalampopoulos, Maxime Crochemore, Costas Iliopoulos, Tomasz Kociumaka, Solon Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen
Efficient enumeration of non-equivalent squares in partial words with few holes

SESSION 8 (Chair: Lusheng Wang)


Edward J. Lee and Serge Gaspers
Faster graph coloring in polynomial space

Sankardeep Chakraborty and Srinivasa Rao Satti
Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications

Aizhong Zhou, Haitao Jiang, Jiong Guo, Haodi Feng, Nan Liu and Binhai Zhu
Improved approximation algorithm for the maximum base pair stackings problem in RNA secondary structures prediction

Saeed Mehrabi
Approximating weighted duo-preservation in comparative genomics


12:10–14:00 Lunch break


14:00–15:40

SESSION 9 (Chair: Qilong Feng)


Wei Yu and Zhaohui Liu
Better inapproximability bounds and approximation algorithms for min-max tree/cycle/path cover problems

Ei Ando and Shuji Kijima
An FPTAS for the volume of some V-polytopes --It is hard to compute the volume of the intersection of two cross-polytopes

Kuan-Yi Ho, Yi-Jun Chang and Hsu-Chun Yen
Unfolding some classes of orthogonal polyhedra of arbitrary genus

Sanjib Sadhu, Sasanka Roy, Subhas Nandy and Suchismita Roy
Optimal covering and hitting of line segments by two axis-parallel squares

SESSION 10 (Chair: Yong Gao)


Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto
Reconfiguration of maximum-weight b-matchings in a graph

Rahnuma Islam Nishat and Sue Whitesides
Bend complexity and Hamiltonian cycles in grid graphs

Satoshi Tayu and Shuichi Ueno
Stable matchings in trees

Jian Xu, Soumya Banerjee, and Wenjing Rao
The existence of universally agreed fairest semi-matchings in any given bipartite graph


15:40–16:10 Coffee & Tea break


16:10–17:50

SESSION 11 (Chair: Hee-Kap Ahn)


Prosenjit Bose, Matias Korman, André van Renssen and Sander Verdonschot
Constrained routing between non-visible vertices

Sumedh Tirodkar and Sundar Vishwanathan
Maximum matching on trees in the online preemptive and the incremental dynamic graph models

Prajakta Nimbhorkar and Arvind Rameshwar V
Dynamic rank-maximal matchings

Wenkai Dai
Reoptimization of minimum latency problem

SESSION 12 (Chair: Donghyun Kim)


Konstantin E. Avrachenkov, Aleksei Yu. Kondratev, and Vladimir V. Mazalov
Cooperative game theory approaches for network partitioning

Pavla Drazdilova, Jan Konecny, and Milos Kudelkas
Chain of influencers: multipartite intra-community ranking

Jing (Selena) He, Ying Xie, Tianyu Du, Shouling Ji, and Zhao Li
Influence spread in social networks with both positive and negative influences

Pavel Krömer and Jana Nowaková
Guided genetic algorithm for the influence maximization problem


18:00–22:00 Banquet (Coaches depart at 18:00 from the conference venue)


August 5 (Saturday)


9:00–10:00

Virginia Vassilevska Williams, Fine-grained complexity of problems in P(Chair: Shang-Hua Teng)


10:00–10:30 Coffee & Tea break


10:30–12:10

SESSION 13 (Chair: Virginia Vassilevska Williams)


Jérémy Barbay, Pablo Pérez-Lantero and Javiel Rojas
Depth distribution in high dimensions

Vladimir Shenmaier
Complexity and algorithms for finding a subset of vectors with the longest sum

Mohammad Ghodsi, Hamid Homapour, and Masoud Seddighin
Approximate minimum diameter

Xuehou Tan and Bo Jiang
Simple O(n log ^2 n) algorithms for the planar 2-center problem

SESSION 14 (Chair: Pavel Krömer)


Suchi Kumari, Anurag Singh, and Hocine Cherifi
Optimal local routing strategies for community structured time varying communication networks

Eliska Ochodkova, Sarka Zehnalova, and Milos Kudelka
Graph construction based on local representativeness

Adam Viktorin, Roman Senkerik, Michal Pluhacek, and Tomas Kadavy
SHADE algorithm dynamic analyzed through complex network

Siman Zhang and Jiping Zheng
An efficient potential member promotion algorithm in social networks via skyline