Fair Allocation of Divisible Goods under Non-Linear Valuations

Haris Aziz, Zixu He, Xinhang Lu, Kaiyang Zhou

AAMAS 2025 Spotlight

This paper addresses the division of homogeneous divisible goods among agents with non-linear valuations. We propose an algorithm that guarantees a $\frac{1}{2n-1}$-MMS allocation for $n$ agents with arbitrary non-decreasing valuations and establish the impossibility of exceeding a $1/n$-MMS approximation, even with one-breakpoint piecewise-constant valuations. For $n\le 3$, the $1/n$ ratio is proven tight. On envy-freeness, we show that verifying the existence of an EF and Pareto optimal (PO) allocation is NP-hard for $n$ agents and at least three goods, even with one-breakpoint piecewise-constant valuations. We complement this with a polynomial-time algorithm for checking EF and PO allocations for a single divisible good with piecewise-linear valuations.

A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

WALCOM 2025 Spotlight

This paper presents piecewise analysis, a new general method that analyzes the running time of branching algorithms. We reanalyze two 17-year-old algorithms from Fomin et al. (2007) that solve 4-Coloring and #3-Coloring and we improve their running time from $O({1.7272}^n)$ to $O({1.7207}^n)$ and from $O({1.6262}^n)$ to $O({1.6225}^n)$ respectively.

[arXiv] [Code]

A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach

Katie Clinch, Serge Gaspers, Zixu He, Simon Mackenzie, Tiankuang Zhang

Submitted to STACS 2025 Spotlight

In this paper, we present a novel algorithm for solving the Vertex Cover problem on subcubic graphs in $O({1.1313}^k)$, beating the previous best running time of $O({1.1442}^k)$ due to Harris and Narayanaswamy (2022). We achieve this by combining two contributions of independent interest: 1) developing a new framework for the automated design of branching algorithms based on the idea of case analysis of local structures, and 2) introducing an extension of Measure & Conquer to randomized branching algorithms.

Fair Railway Network Design

Zixu He, Sirin Botan, Jérôme Lang, Abdallah Saffidine, Florian Sikora, Silas Workman

Submitted to AAAI 2025

When designing a public transportation network in a country, one may want to minimise the sum of travel duration of all inhabitants. This corresponds to a purely utilitarian view and does not involve any fairness consideration, as the resulting network will typically benefit the capital city and/or large central cities while leaving some peripheral cities behind. On the other hand, a more egalitarian view will allow some people to travel between peripheral cities without having to go through a central city. We define a model, propose algorithms for computing solution networks, and report on experiments based on real data.

[arXiv]