Author name cluster

Vincent Chau

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.

9 papers

2 author rows

AAAI Conference 2025 Conference Paper

Facility Location Games with Optional Preferences: A Revisit

Xingchen Sha
Shuyu Bao
Hau Chan
Vincent Chau
Ken C. K. Fong
Minming Li

We study the k-facility location games with optional preferences on the line. In the games, each strategic agent has a public location preference on the k facility locations and a private optional preference on the preferred/acceptable set of facilities out of the k facilities. Our goal is to design strategyproof mechanisms to elicit agents’ optional preferences and locate k facilities to minimize the social or maximum cost of agents based on their facility preferences and public agent locations. We consider two variants of the facility location games with optional preferences: the Min variant and the Max variant where the agent’s cost is defined as their distance to the closest acceptable facility and the farthest acceptable facility, respectively. For the Min variant, we present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost with k ≥ 3 facilities, achieving approximation ratios of 3 and 2n+1 respectively. We complement the results by establishing lower bounds of 3/2 and n/4 for the approximation ratios achievable by any deterministic strategyproof mechanisms for the maximum cost and social cost, respectively. We then improve our results in a special setting of the Min variant where there are exactly three facilities and present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost. For the Max variant, we present an optimal deterministic strategyproof mechanism for the maximum cost and a k-approximation deterministic strategyproof mechanism for the social cost.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction

Yixuan Li
Can Chen
Jiajun Li
Jiahui Duan
Xiongwei Han
Tao Zhong
Vincent Chau
Weiwei Wu

By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.

PDF Details DOI

ECAI Conference 2025 Conference Paper

Mechanism Design for Facility Location Problems with Capacity Constraints in Bounded Location Space

Xingchen Sha
Hau Chan
Vincent Chau
Ken C. K. Fong
Minming Li
Wai Lun Lo

We consider the k-facility location problems with capacity constraints in bounded location space from the mechanism design perspective. In this problem, we seek to locate k capacity constrained facilities in a bounded interval (i. e. , B=[bl, br]) to serve agents, who have preferences on the ideal locations of the facilities in the interval. Our goal is to design strategyproof mechanisms to elicit agents’ true ideal locations and locate facilities that minimize the social cost and maximum cost, which are defined to be the sum and the maximum of the agents’ costs (i. e. , agents’ distances to their facilities), respectively. For the equal capacity setting without spare capacity (i. e. , all the agents can be served exactly), we provide a deterministic strategyproof mechanism. For any bounded interval (i. e. , bl, br∈R), our mechanism has approximation ratios of n-1 for the social cost and 4 for the maximum cost with k≥3 facilities and n≥3 agents. We also establish lower bounds of n/2 for the social cost by a common class of deterministic mechanisms that order agents from left to right, and 2 for the maximum cost by any deterministic mechanism. Our mechanism also achieves tight bounds for both costs with k<3 facilities. We then consider the equal capacity setting with spare capacity and the arbitrary capacity setting without spare capacity. For these two settings and any bounded interval, we provide randomized strategyproof mechanisms with approximation ratios of n/2 for the social cost and 2 for the maximum cost with any number of facilities. We complement this result by establishing lower bounds of 5/3 for the social cost and 3/2 for the maximum cost.

Details

AAAI Conference 2023 Conference Paper

Multi-Stage Facility Location Problems with Transient Agents

Xuezhen Wang
Vincent Chau
Hau Chan
Ken C.K. Fong
Minming Li

We study various models for the one-dimensional multi-stage facility location problems with transient agents, where a transient agent arrives in some stage and stays for a number of consecutive stages. In the problems, we need to serve each agent in one of their stages by determining the location of the facility at each stage. In the first model, we assume there is no cost for moving the facility across the stages. We focus on optimal algorithms to minimize both the social cost objective, defined as the total distance of all agents to the facility over all stages, and the maximum cost objective, defined as the max distance of any agent to the facility over all stages. For each objective, we give a slice-wise polynomial (XP) algorithm (i.e., solvable in m^f(k) for some fixed parameter k and computable function f, where m is the input size) and show that there is a polynomial-time algorithm when a natural first-come-first-serve (FCFS) order of agent serving is enforced. We then consider the mechanism design problem, where the agents' locations and arrival stages are private, and design a group strategy-proof mechanism that achieves good approximation ratios for both objectives and settings with and without FCFS ordering. In the second model, we consider the facility's moving cost between adjacent stages under the social cost objective, which accounts for the total moving distance of the facility. Correspondingly, we design XP (and polynomial time) algorithms and a group strategy-proof mechanism for settings with or without the FCFS ordering.

PDF Details DOI

TCS Journal 2021 Journal Article

Minimizing energy on homogeneous processors with shared memory

Vincent Chau
Chi Kit Ken Fong
Shengxin Liu
Elaine Yinling Wang
Yong Zhang

Energy efficiency is a crucial desideratum in the design of computer systems, from small-sized mobile devices with limited battery to large scale data centers. In such computing systems, processors and memory are considered as two major power consumers among all the system components. One recent trend to reduce power consumption is using shared memory in multi-core systems, such architecture has become ubiquitous nowadays. However, implementing the energy-efficient methods to the multi-core processor and the shared memory separately is not trivial. In this work, we consider the energy-efficient task scheduling problem, which coordinates the power consumption of both the multi-core processor and the shared memory, especially focus on the general situation in which the number of tasks is more than the number of cores. We devise an approximation algorithm with guaranteed performance in the multiple cores system. We tackle the problem by first presenting an optimal algorithm when the assignment of tasks to cores is given. Then we propose an approximation assignment for the general task scheduling.

Details DOI

TCS Journal 2021 Journal Article

Scheduling with variable-length calibrations: Two agreeable variants

Hua Chen
Lin Chen
Guochuan Zhang
Vincent Chau

Machines usually require maintenance after running a fixed period. A calibration at a cost has to be performed during the process. Finding a feasible schedule minimizing the total cost of calibrations is of great importance. In this paper, we deal with a single machine scheduling model with K types of calibrations. A calibration of type k ∈ { 1, …, K } can be made instantaneously at any time point, which incurs a cost f k and can keep the machine active for a length T k. Given a set of n jobs with release times, deadlines, and processing times, the goal is to minimize the total cost of calibrations by assigning all jobs in the calibrated state, where job preemption is allowed. We investigate two agreeable settings. Regarding agreeable jobs, later release times imply later deadlines. We establish a pseudo-polynomial time optimal algorithm and a ( 3 + ε ) -approximation algorithm. Moreover, if the largest job processing time is no more than any calibration length, it admits a ( 2 + ε ) -approximation algorithm. As for agreeable calibrations, where the cost of each calibration is proportional to its length, a 2-approximation algorithm is presented.

Details DOI

TCS Journal 2020 Journal Article

Flow shop for dual CPUs in dynamic voltage scaling

Vincent Chau
Xin Chen
Ken C.K. Fong
Minming Li
Kai Wang

We study the following flow shop scheduling problem on two processors. We are given n jobs with a common deadline D, where each job j has workload p i, j on processor i and a set of processors which can vary their speed dynamically. Job j can be executed on the second processor if the execution of job j is completed on the first processor. Our objective is to find a feasible schedule such that all jobs are completed by the common deadline D with minimized energy consumption. For this model, we present a linear program for the discrete speed case, where the processor can only run at specific speeds in S = { s 1, s 2, ⋯, s q } and the job execution order is fixed. We also provide a m α − 1 -approximation algorithm for the arbitrary order case and for continuous speed model where m is the number of processors and α is a parameter of the processor. We then introduce a new variant of flow shop scheduling problem called sense-and-aggregate model motivated by data aggregation in wireless sensor networks where the base station needs to receive data from sensors and then compute a single aggregate result. In this model, the first processor will receive unit size data from sensors and the second processor is responsible for calculating the aggregate result. The second processor can decide when to aggregate and the workload that needs to be done to aggregate x data will be f ( x ) and another unit size data will be generated as the result of the partial aggregation which will then be used in the next round aggregation. Our objective is to find a schedule such that all data are received and aggregated by the deadline with minimum energy consumption. We present an O ( n 5 ) dynamic programming algorithm when f ( x ) = x and a greedy algorithm when f ( x ) = x − 1. Finally, we investigate the performance of the flowshop problem when the order of jobs is fixed by comparing it to the approximation algorithm with an arbitrary order. We show experimentally that the approximation ratio is close to 1 when there are few machines and when there are more jobs.

Details DOI

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

TCS Journal 2016 Journal Article

Throughput maximization in multiprocessor speed-scaling

Eric Angel
Evripidis Bampis
Vincent Chau
Nguyen Kim Thang

In the classical energy minimization problem, introduced in [24], we are given a set of n jobs each one characterized by its release date, its deadline, its processing volume and we aim to find a feasible schedule of the jobs on a single speed-scalable machine so that the total energy consumption is minimized. Here, we study the throughput maximization version of the problem where we are given a budget of energy E and where every job has also a value. Our goal is to determine a feasible schedule maximizing the (weighted) throughput of the jobs that are executed between their respective release dates and deadlines. We first consider the preemptive non-migratory multiprocessor case in a fully heterogeneous environment in which every job has a machine-dependent release date, deadline and processing volume and every machine obeys to a different speed-to-power function. We present a polynomial time greedy algorithm based on the primal-dual scheme that approximates the optimum solution within a factor depending on the energy functions (the factor is constant for typical energy functions of form P ( z ) = z α ). Then, we focus on the non-preemptive case for which we consider a fixed number of identical parallel machines and two important families of instances: (1) equal processing volume jobs; and (2) agreeable jobs. For both cases we present optimal pseudo-polynomial-time algorithms.

Details DOI