Author name cluster

Ruilong Zhang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

1 author row

AAMAS Conference 2026 Conference Paper

Multiagent Matroid Upgrading: Greedy is Fair and Efficient

Qingwen Ma
Chao Peng
Changfeng Xu
Chenyang Xu
Ruilong Zhang

This paper introduces a general multiagent matroid upgrading problem that models a broad class of real-world resource allocation tasks. In this setting, there are multiple agents and a ground set of elements, where each element is assigned to a specific agent and has two associated costs: a default cost and a reduced (upgraded) cost. Upgrading an element lowers its cost to the upgraded value, while non-upgraded elements retain their default costs. Each agent is associated with its own matroid, with the goal of finding a minimum-cost basis. The central task is to select at most𝑘 elements to upgrade so as to minimize a non-decreasing convex function over the agents’ minimum basis costs, capturing both efficiency and fairness objectives in multiagent systems. We show that the problem is polynomial-time solvable and that an optimal solution can be obtained via a simple greedy algorithm. Our analysis exploits the structural properties of matroids to establish the existence of optimal substructures, thereby ensuring that greedy upgrading yields optimal outcomes. Building on this insight, we can further extend our result to more general settings, such as scenarios with interval fairness constraints, where the number of elements upgraded for each agent is required to lie within a specified interval.

PDF

NeurIPS Conference 2025 Conference Paper

A Beyond-Worst-Case Analysis of Greedy k-means++

Qingyun Chen
Sungjin Im
Ben Moseley
Ryan Milstrey
Chenyang Xu
Ruilong Zhang

$k$-means++ and the related greedy $k$-means++ algorithm are celebrated algorithms that efficiently compute seeds for Lloyd's algorithm. Greedy $k$-means++ is a generalization of $k$-means++ where, in each iteration, a new seed is greedily chosen among multiple $\ell \geq 2$ points sampled, as opposed to a single seed being sampled in $k$-means++. While empirical studies consistently show the superior performance of greedy $k$-means++, making it a preferred method in practice, a discrepancy exists between theory and practice. No theoretical justification currently explains this improved performance. Indeed, the prevailing theory suggests that greedy $k$-means++ exhibits worse performance than $k$-means++ in worst-case scenarios. This paper presents an analysis demonstrating the outperformance of the greedy algorithm compared to $k$-means++ for a natural class of well-separated instances with exponentially decaying distributions, such as Gaussian, specifically when $\ell = \Theta(\log k)$, a common parameter setting in practical applications.

PDF Details

IJCAI Conference 2025 Conference Paper

Fair Submodular Maximization over a Knapsack Constraint

Lijun Li
Chenyang Xu
Liuyi Yang
Ruilong Zhang

We consider fairness in submodular maximization subject to a knapsack constraint, a fundamental problem with various applications in economics, machine learning, and data mining. In the model, we are given a set of ground elements, each associated with a cost and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total cost does not exceed a specified budget (the knapsack constraint) and that the number of elements selected for each color falls within a designated range (the fairness constraint). While there exists some recent literature on this topic, the existence of a non-trivial approximation for the problem -- without relaxing either the knapsack or fairness constraints -- remains a challenging open question. This paper makes progress in this direction. We demonstrate that when the number of colors is constant, there exists a polynomial-time algorithm that achieves a constant approximation with high probability. Additionally, we show that if either the knapsack or fairness constraint is relaxed only to require expected satisfaction, a tight approximation ratio of (1-1/e-epsilon) can be obtained in expectation for any epsilon >0.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Logarithmic Approximations for Fair k-Set Selection

Shi Li
Chenyang Xu
Ruilong Zhang

We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i. e. , the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G: =(L cup R, E), our problem is equivalent to selecting k vertices from R such that the maximum (weighted) number selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research. We first prove that the problem is NP-hard even if the maximum degree Delta of the input bipartite graph is 3, and the problem is in P when Delta=2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O(log n/(log log n))-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log(Delta))-approximation on bipartite graphs with a maximum degree Delta. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Public Event Scheduling with Busy Agents

Bo Li
Lijun Li
Minming Li
Ruilong Zhang

We study a public event scheduling problem, where multiple public events are scheduled to coordinate the availability of multiple agents. The availability of each agent is determined by solving a separate flexible interval job scheduling problem, where the jobs are required to be preemptively processed. The agents want to attend as many events as possible, and their agreements are considered to be the total length of time during which they can attend these events. The goal is to find a schedule for events as well as the job schedule for each agent such that the total agreement is maximized. We first show that the problem is NP-hard, and then prove that a simple greedy algorithm achieves 1/2-approximation when the whole timeline is polynomially bounded. Our method also implies a (1-1/e)-approximate algorithm for this case. Subsequently, for the general timeline case, we present an algorithmic framework that extends a 1/alpha-approximate algorithm for the one-event instance to the general case that achieves 1/(alpha+1)-approximation. Finally, we give a polynomial time algorithm that solves the one-event instance, and this implies a 1/2-approximate algorithm for the general case.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Sampling for Beyond-Worst-Case Online Ranking

Qingyun Chen
Sungjin Im
Benjamin Moseley
Chenyang Xu
Ruilong Zhang

The feedback arc set problem is one of the most fundamental and well-studied ranking problems where n objects are to be ordered based on their pairwise comparison. The problem enjoys several efficient approximation algorithms in the offline setting. Unfortunately, online there are strong lower bounds on the competitive ratio establishing that no algorithm can perform well in the worst case. This paper introduces a new beyond-worst-case model for online feedback arc set. In the model, a sample of the input is given to the algorithm offline before the remaining instance is revealed online. This models the case in practice where yesterday's data is available and is similar to today's online instance. This sample is drawn from a known distribution which may not be uniform. We design an online algorithm with strong theoretical guarantees. The algorithm has a small constant competitive ratio when the sample is uniform---if not, we show we can recover the same result by adding a provably minimal sample. Empirical results validate the theory and show that such algorithms can be used on temporal data to obtain strong results.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Min-Max Submodular Ranking for Multiple Agents

Qingyun Chen
Sungjin Im
Benjamin Moseley
Chenyang Xu
Ruilong Zhang

In the submodular ranking (SR) problem, the input consists of a set of submodular functions defined on a ground set of elements. The goal is to order elements for all the functions to have value above a certain threshold as soon on average as possible, assuming we choose one element per time. The problem is flexible enough to capture various applications in machine learning, including decision trees. This paper considers the min-max version of SR where multiple instances share the ground set. With the view of each instance being associated with an agent, the min-max problem is to order the common elements to minimize the maximum objective of all agents---thus, finding a fair solution for all agents. We give approximation algorithms for this problem and demonstrate their effectiveness in the application of finding a decision tree for multiple agents.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Multiagent MST Cover: Pleasing All Optimally via a Simple Voting Rule

Bo Li
Xiaowei Wu
Chenyang Xu
Ruilong Zhang

Given a connected graph on whose edges we can build roads to connect the nodes, a number of agents hold possibly different perspectives on which edges should be selected by assigning different edge weights. Our task is to build a minimum number of roads so that every agent has a spanning tree in the built subgraph whose weight is the same as a minimum spanning tree in the original graph. We first show that this problem is NP-hard and does not admit better than ((1-o(1)) ln k)-approximation polynomial-time algorithms unless P = NP, where k is the number of agents. We then give a simple voting algorithm with an optimal approximation ratio. Moreover, our algorithm only needs to access the agents' rankings on the edges. Finally, we extend our problem to submodular objective functions and Matroid rank constraints.

PDF Details DOI

TCS Journal 2022 Journal Article

Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves models

Benjamin Moselely
Ruilong Zhang
Shanjiawen Zhao

This paper considers scheduling jobs online on m identical machines such that the jobs can be parallelized across the machines. Two models of parallelizability are considered, one is the speed-up curves model, and the other is the directed-acyclic-graph (DAG) model. For both models, the objectives considered are the average, maximum, and ℓ k -norms of flow time for k ≥ 1. We establish an Ω ( m ) lower bound on the competitive ratio of any algorithm for optimizing average flow time in both models without resource augmentation. With resource augmentation, we give a ( 1 + ϵ ) -speed O ( 1 ϵ 2 k + 1 ) -competitive algorithm in the DAG model for the ℓ k -norms of flow time. This essentially matches the best-known result in the speed-up curve model for the ℓ k -norms of flow time. Finally, we show an O ( 1 ) -competitive algorithm for minimizing the maximum flow time in the speed-up curves model.

Details DOI

NeurIPS Conference 2021 Conference Paper

Fair Scheduling for Time-dependent Resources

Bo Li
Minming Li
Ruilong Zhang

We study a fair resource scheduling problem, where a set of interval jobs are to be allocated to heterogeneous machines controlled by intellectual agents. Each job is associated with release time, deadline, and processing time such that it can be processed if its complete processing period is between its release time and deadline. The machines gain possibly different utilities by processing different jobs, and all jobs assigned to the same machine should be processed without overlap. We consider two widely studied solution concepts, namely, maximin share fairness and envy-freeness. For both criteria, we discuss the extent to which fair allocations exist and present constant approximation algorithms for various settings.

PDF Details

TCS Journal 2020 Journal Article

Minimizing the cost of batch calibrations

Vincent Chau
Minming Li
Elaine Yinling Wang
Ruilong Zhang
Yingchao Zhao

We study the scheduling problem with calibrations. We are given a set of n jobs that need to be scheduled on a set of m machines. However, a machine can schedule jobs only if a calibration has been performed beforehand and the machine is considered as valid during a fixed time period of T, after which it must be recalibrated before running more jobs. In this paper, we investigate the batch calibrations; calibrations occur in batch and at the same moment. It is then not possible to perform any calibrations during a period of T. We consider different cost function depending on the number of machines we calibrate at a given time, i. e. , the cost function is denoted as f ( x ) where x is the number of calibrations in the batch. Moreover, jobs have release time, deadline, and unit processing time. The objective is to schedule all jobs with the minimum cost of calibrations. We give a dynamic program to solve the case with an arbitrary cost function. Then, we propose several faster approximation algorithms for different cost functions: an optimal algorithm when f ( x ) = b, a 3-approximation algorithm when f ( x ) = x and a ( m + b ) / ( b + 1 ) -approximation algorithm when f ( x ) = x + b. The running time of these algorithms are O ( n 2 ).

Details DOI