Mode: Mixed
Achieving fairness in resource allocation can be modelled as a graph-based optimization problem, with many efficient algorithms available. This talk explores the connection between market equilibrium and graph density decomposition, showing how fast convergence can be achieved in large-scale systems. We present a unified framework linking hypergraph density decomposition and Fisher market equilibrium through locally verifiable optimality conditions. This symmetry allows repurposing algorithms between domains, significantly accelerating convergence.
We focus on iterative gradient-based methods, including the iterative proportional response process and its momentum-enhanced extensions. Our novel exponential momentum approach refines traditional techniques, delivering near-optimal solutions in distributed settings. Empirical results show these methods outperform existing algorithms, achieving speedups by several orders of magnitude in large-scale graphs.
By integrating graph theory, market dynamics, and optimization, this talk offers new insights into efficient computation to achieve fairness in networked systems. These methods deepen our understanding of algorithmic principles and open new applications in algorithm design, social networks, and economic modelling.
Professor Hubert Chan completed his PhD in Computer Science at Carnegie Mellon University in 2007. Before taking up the faculty position at HKU in 2009, he spent two years as a post-doc at Max Planck Institute for Informatics in Germany. His main research interests are approximation algorithms, discrete metric space, privacy and security inspired problems.
Clean water and clean air are vital for public health. This project focuses on developing high-efficiency and environmentally sustainable filters for removing harmful air/water pollutants. The team has developed novel architectures and functionalities for the filters to achieve high permeance, high removal efficiency, and excellent reusability.
