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 \leq 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]