Title: A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization

Speaker: Philip Cervenjak
University of Melbourne

Summary:

The problem of Directed Connected Submodular Maximization (DCSM) captures a number of important network design problems, such as deploying a connected network of unmanned aerial vehicles, wireless routers, or wireless sensors with maximum coverage. It also captures the problem of selecting a connected pathway of gene mutations that best explain the presence of cancer. Formally, an instance ofDCSM consists of a directed graph G, an integer k, and a non-negative monotone submodular function f that assigns a value to each subset of G’s vertices; the submodularity of f means that every vertex has diminishing marginal gains. The goal of DCSM is to select a directed out-tree in G, with at most k edges, whose vertices maximize f.

DCSM is considered to be a challenging problem; in the worst-case, previous efficient (i.e., polynomial time) algorithms achieve an approximation factor ofOmega(1/sqrt{k}) (i.e., they find a solution whose value is within this factor of the optimum). It is possible to achieve a tighter approximation factor depending on the radius of the optimal out-tree, r, which is the maximum length of a directed path starting at the root vertex; the value of r is small in highly connected networks and is no larger than k. However, previous efficient algorithms only achieve an approximation factor of Omega(1/r); ideally, the dependence on r in the approximation factor would match the best dependence on k.

In our recent work, we present an efficient algorithmic framework for DCSM that achieves, for any fixed eps between 0 and 1, an approximation factor of Omega(1/r^{eps}); this improves on prior work with respect to both k and r when eps< 1/2. The main algorithm in our framework is GreedyRadius, which converts another algorithm’s approximation factor depending on k to essentially the same approximation factor depending on r. The second algorithm in our framework is RecApprox, which implies an approximation factor of Omega(1/k^{eps}). Combining GreedyRadius and RecApprox gives our main result. Further, our algorithmic framework can handle the variant of DCSM where the root of the out-tree is specified, albeit returning an out-tree that violates the size constraint, k, by a constant factor.

Bio: 
Philip is a final-year PhD student in the School of Computing and Information Systems at the University of Melbourne, and is supervised by Dr. Junhao Gan, Dr. Seeun William Umboh, and Prof. Anthony Wirth. His PhD research is on designing approximation algorithms for submodular optimization problems that achieve beyond-worst-case performance. He has published two conference papers so far, and has visited Keio University in Japan to work with Prof. Naonori Kakimura on the Connected Submodular Maximization problem. Before his PhD, Philip completed a Master of Science (Computer Science) and a Bachelor of Science, both at the University of Melbourne.

—

This event is Hybrid:
ATTEND IN PERSON – MELBOURNE CONNECT, LEVEL 8, ROOM 8109, 700 SWANSTON STREET, CARLTON
ZOOM – MEETING ID: 873 1557 5255; PASSWORD: 778635

SEMINAR: WED 23 JULY 2025 16:00-17:00 (AEST, Melbourne Time)