Chao Xu 0002

ECAI Conference 2025 Conference Paper

Efficient Branch-and-Bound for Submodular Function Maximization Under Knapsack Constraint

• Yimin Hao
• Yi Zhou 0016
• Chao Xu 0002
• Zhang-Hua Fu

The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimization problem. The majority of existing approaches to solving the SKP are approximation algorithms. However, in domains such as health-care facility location and risk management, the need for optimal solutions is still critical, necessitating the use of exact algorithms over approximation methods. In this paper, we present an optimal branch-and-bound approach, featuring a novel upper bound with a worst-case tightness guarantee and an efficient dual branching method to minimize repeated computations. Experiments in applications such as facility location, weighted coverage, influence maximization, and so on show that the algorithms that implement the new ideas are far more efficient than conventional methods.

SODA Conference 2023 Conference Paper

A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function

• Tsuyoshi Hirayama
• Yuhao Liu 0003
• Kazuhisa Makino
• Ke Shi
• Chao Xu 0002

In this paper, we study the minimum k -partition problem of submodular functions, i. e. , given a finite set V and a submodular function f: 2 V → ℝ, computing a k -partition { V 1, …, V k } of V with minimum. The problem is a natural generalization of the minimum k -cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for k ≤ 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem. * Authors are ordered alphabetically.

MFCS Conference 2022 Conference Paper

Improved Approximation Algorithms for the Traveling Tournament Problem

• Jingyang Zhao 0001
• Mingyu Xiao 0001
• Chao Xu 0002

The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other’s home venue, minimizing the total distance traveled by all n teams (n is even). TTP-k is the problem with one more constraint that each team can have at most k consecutive home games or away games. The case where k = 3, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from (1. 667+ε) to (1. 598+ε), for any ε > 0. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to k ≥ 4. We demonstrate that the approximation ratio of TTP-4 can be improved from (1. 750+ε) to (1. 700+ε) by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from 4/3 to (6/5+ε).

SODA Conference 2018 Conference Paper

Hypergraph k -Cut in Randomized Polynomial Time

• Karthekeyan Chandrasekaran
• Chao Xu 0002
• Xilin Yu

SODA Conference 2017 Conference Paper

A Faster Pseudopolynomial Time Algorithm for Subset Sum

• Konstantinos Koiliaris
• Chao Xu 0002

Given a multiset S of n positive integers and a target integer t, the subset sum problem is to decide if there is a subset of S that sums up to t. We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer u in where σ is the sum of all elements in S and Õ hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in O ( nu ) time. To the best of our knowledge, the new algorithm is the fastest general deterministic algorithm for this problem. We also present a modified algorithm for finite cyclic groups, which computes all the realizable subset sums within the group in time, where m is the order of the group.

SODA Conference 2017 Conference Paper

Computing minimum cuts in hypergraphs

• Chandra Chekuri
• Chao Xu 0002

We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph H = ( V, E ) with n = │V│, m = |E| and p = Σ e∊E l e l the fastest known algorithm to compute a global minimum cut in H runs in O ( np ) time for the uncapacitated case, and in O ( np + n 2 log n ) time for the capacitated case. We show the following new results. Given an uncapacitated hypergraph H and an integer k we describe an algorithm that runs in O (p) time to find a subhypergraph H ’ with sum of degrees O ( kn ) that preserves all edge-connectivities up to k (a k -sparsifier). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an O ( p + Λ n 2 ) time algorithm for computing a global minimum cut of H where λ is the minimum cut value. We generalize Matula's argument for graphs to hy- pergraphs and obtain a (2 + ∊ )-approximation to the global minimum cut in a capacitated hypergraph in time, and in in O ( p / ∊ ) time for uncapacitated hypergraphs. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O ( np + n 2 log n ) time and O (p) space. Our results build upon properties of vertex orderings that were inspired by the maximum adjacency ordering for graphs due to Nagamochi and Ibaraki. Unlike graphs we observe that there are several different orderings for hypergraphs which yield different insights.

SODA Conference 2015 Conference Paper

Detecting Weakly Simple Polygons

• Hsien-Chih Chang
• Jeff Erickson 0001
• Chao Xu 0002

A closed curve in the plane is weakly simple if it is the limit (in the Fréchet metric) of a sequence of simple closed curves. We describe an algorithm to determine whether a closed walk of length n in a simple plane graph is weakly simple in O ( n log n ) time, improving an earlier O ( n 3 )-time algorithm of Cortese et al. [ Discrete Math. 2009]. As an immediate corollary, we obtain the first efficient algorithm to determine whether an arbitrary n -vertex polygon is weakly simple; our algorithm runs in O ( n 2 log n ) time. We also describe algorithms that detect weak simplicity in O ( n log n ) time for two interesting classes of polygons. Finally, we discuss subtle errors in several previously published definitions of weak simplicity.