Chenyang Xu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Chenyang Xu has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Ruilong Zhang
University at Buffalo
4 shared publications - Ruilong Zhang
Technical University of Munich
4 shared publications - Zhengfeng Yang
East China Normal University, Shanghai, Shanghai, China
4 shared publications - Benjamin Moseley
Carnegie Mellon University, Pittsburgh, PA, USA
3 shared publications - Chao Peng
East China Normal University
3 shared publications - Sungjin Im
Computer Science and Engineering, University of California, Santa Cruz, Santa Cruz, CA, USA
3 shared publications
Latest Publications
- Open Access
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3943-3951
Logarithmic Approximations for Fair k-Set Selection
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.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3943-3951
Open AccessLogarithmic Approximations for Fair k-Set Selection
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.
- Open Access
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3934-3942
Fair Submodular Maximization over a Knapsack Constraint
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.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3934-3942
Open AccessFair Submodular Maximization over a Knapsack Constraint
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.
- 30 June 2025
- Published by Springer Nature
- p. 400-414
Mechanism Design for Auctions with Externalities on Budgets
- 30 June 2025
- Published by Springer Nature
- p. 400-414
Mechanism Design for Auctions with Externalities on Budgets
- Open Access
Fair Submodular Maximization over a Knapsack Constraint
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 weight and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total weight 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-ε)$ can be obtained in expectation for any $ε>0$.Open AccessFair Submodular Maximization over a Knapsack Constraint
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 weight and a color, and a monotone submodular function defined over them. The goal is to maximize the submodular function while guaranteeing that the total weight 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-ε)$ can be obtained in expectation for any $ε>0$. - Open Access
Logarithmic Approximations for Fair k-Set Selection
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 total weight of 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 $Δ$ of the input bipartite graph is $3$, and the problem is in P when $Δ=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 a dependent rounding algorithm achieves $O(\frac{\log n}{\log \log n})$-approximation on general bipartite graphs, and an independent rounding algorithm achieves $O(\logΔ)$-approximation on bipartite graphs with a maximum degree $Δ$. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming. Finally, we extend all our algorithms to the weighted case and prove that all approximations are preserved.Open AccessLogarithmic Approximations for Fair k-Set Selection
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 total weight of 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 $Δ$ of the input bipartite graph is $3$, and the problem is in P when $Δ=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 a dependent rounding algorithm achieves $O(\frac{\log n}{\log \log n})$-approximation on general bipartite graphs, and an independent rounding algorithm achieves $O(\logΔ)$-approximation on bipartite graphs with a maximum degree $Δ$. We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming. Finally, we extend all our algorithms to the weighted case and prove that all approximations are preserved. - Open Access
Mechanism Design for Auctions with Externalities on Budgets
This paper studies mechanism design for auctions with externalities on budgets, a novel setting where the budgets that bidders commit are adjusted due to the externality of the competitors' allocation outcomes-a departure from traditional auctions with fixed budgets. This setting is motivated by real-world scenarios, for example, participants may increase their budgets in response to competitors' obtained items. We initially propose a general framework with homogeneous externalities to capture the interdependence between budget updates and allocation, formalized through a budget response function that links each bidder's effective budget to the amount of items won by others. The main contribution of this paper is to propose a truthful and individual rational auction mechanism for this novel auction setting, which achieves an approximation ratio of $1/3$ with respect to the liquid welfare. This mechanism is inspired by the uniform-price auction, in which an appropriate uniform price is selected to allocate items, ensuring the monotonicity of the allocation rule while accounting for budget adjustments. Additionally, this mechanism guarantees a constant approximation ratio by setting a purchase limit. Complementing this result, we establish an upper bound: no truthful mechanism can achieve an approximation ratio better than $1/2$. This work offers a new perspective to study the impact of externalities on auctions, providing an approach to handle budget externalities in multi-agent systems.Open AccessMechanism Design for Auctions with Externalities on Budgets
This paper studies mechanism design for auctions with externalities on budgets, a novel setting where the budgets that bidders commit are adjusted due to the externality of the competitors' allocation outcomes-a departure from traditional auctions with fixed budgets. This setting is motivated by real-world scenarios, for example, participants may increase their budgets in response to competitors' obtained items. We initially propose a general framework with homogeneous externalities to capture the interdependence between budget updates and allocation, formalized through a budget response function that links each bidder's effective budget to the amount of items won by others. The main contribution of this paper is to propose a truthful and individual rational auction mechanism for this novel auction setting, which achieves an approximation ratio of $1/3$ with respect to the liquid welfare. This mechanism is inspired by the uniform-price auction, in which an appropriate uniform price is selected to allocate items, ensuring the monotonicity of the allocation rule while accounting for budget adjustments. Additionally, this mechanism guarantees a constant approximation ratio by setting a purchase limit. Complementing this result, we establish an upper bound: no truthful mechanism can achieve an approximation ratio better than $1/2$. This work offers a new perspective to study the impact of externalities on auctions, providing an approach to handle budget externalities in multi-agent systems. - Open Access
CuDIP: Enhancing Theorem Proving in LLMs via Curriculum Learning-based Direct Preference Optimization
Automated theorem proving (ATP) is one of the most challenging mathematical reasoning tasks for Large Language Models (LLMs). Most existing LLM-based ATP methods rely on supervised fine-tuning, which results in a limited alignment between the theorem proving process and human preferences. Direct Preference Optimization (DPO), which aligns LLMs with human preferences, has shown positive effects for certain tasks. However, the lack of high-quality preference data for theorem proving presents a significant challenge. In this paper, we innovatively apply DPO to formal automated theorem proving and introduces a Curriculum Learning-based DPO Iterative Theorem Proving (CuDIP) method. Specifically, we propose a method for constructing preference data which utilizes LLMs and existing theorem proving data to enhance the diversity of the preference data while reducing the reliance on human preference annotations. We then integrate this preference data construction method with curriculum learning to iteratively fine-tune the theorem proving model through DPO. Experimental results on the MiniF2F and ProofNet datasets demonstrate the effectiveness of the proposed method.
Open AccessCuDIP: Enhancing Theorem Proving in LLMs via Curriculum Learning-based Direct Preference Optimization
Automated theorem proving (ATP) is one of the most challenging mathematical reasoning tasks for Large Language Models (LLMs). Most existing LLM-based ATP methods rely on supervised fine-tuning, which results in a limited alignment between the theorem proving process and human preferences. Direct Preference Optimization (DPO), which aligns LLMs with human preferences, has shown positive effects for certain tasks. However, the lack of high-quality preference data for theorem proving presents a significant challenge. In this paper, we innovatively apply DPO to formal automated theorem proving and introduces a Curriculum Learning-based DPO Iterative Theorem Proving (CuDIP) method. Specifically, we propose a method for constructing preference data which utilizes LLMs and existing theorem proving data to enhance the diversity of the preference data while reducing the reliance on human preference annotations. We then integrate this preference data construction method with curriculum learning to iteratively fine-tune the theorem proving model through DPO. Experimental results on the MiniF2F and ProofNet datasets demonstrate the effectiveness of the proposed method.
- 20 February 2025
- Published by Springer Nature
- p. 79-91
Resource-Limited Network Security Games with General Contagious Attacks
- 20 February 2025
- Published by Springer Nature
- p. 79-91
Resource-Limited Network Security Games with General Contagious Attacks
- 20 February 2025
- Published by Springer Nature
- p. 53-65
Sponsored Search Auction Design Beyond Single Utility Maximization
- 20 February 2025
- Published by Springer Nature
- p. 53-65
Sponsored Search Auction Design Beyond Single Utility Maximization
- Open Access
How to Balance the Load Online When Jobs and Machines Are Both Selfish?
In this paper, we study the classic optimization problem of Related Machine Online Load Balancing under the conditions of selfish machines and selfish jobs. We have $m$ related machines with varying speeds and $n$ jobs arriving online with different sizes. Our objective is to design an online truthful algorithm that minimizes the makespan while ensuring that jobs and machines report their true sizes and speeds. Previous studies in the online scenario have primarily focused on selfish jobs, beginning with the work of Aspnes et al. (JACM 1997). An $O(1)$-competitive online mechanism for selfish jobs was discovered by Feldman, Fiat, and Roytman (EC 2017). For selfish machines, truthful mechanisms have only been explored in offline settings, starting with Archer and Tardos (FOCS 2001). The best-known results are two PTAS mechanisms by Christodoulou and Kovács (SICOMP 2013) and Epstein et al. (MOR 2016). We design an online mechanism that is truthful for both machines and jobs, achieving a competitive ratio of $O(\log m)$. This is the first non-trivial two-sided truthful mechanism for online load balancing and also the first non-trivial machine-side truthful mechanism. Furthermore, we extend our mechanism to the $\ell_q$ norm variant of load balancing, maintaining two-sided truthfulness with a competitive ratio of $\tilde{O}(m^{\frac{1}{q}(1-\frac{1}{q})})$.Open AccessHow to Balance the Load Online When Jobs and Machines Are Both Selfish?
In this paper, we study the classic optimization problem of Related Machine Online Load Balancing under the conditions of selfish machines and selfish jobs. We have $m$ related machines with varying speeds and $n$ jobs arriving online with different sizes. Our objective is to design an online truthful algorithm that minimizes the makespan while ensuring that jobs and machines report their true sizes and speeds. Previous studies in the online scenario have primarily focused on selfish jobs, beginning with the work of Aspnes et al. (JACM 1997). An $O(1)$-competitive online mechanism for selfish jobs was discovered by Feldman, Fiat, and Roytman (EC 2017). For selfish machines, truthful mechanisms have only been explored in offline settings, starting with Archer and Tardos (FOCS 2001). The best-known results are two PTAS mechanisms by Christodoulou and Kovács (SICOMP 2013) and Epstein et al. (MOR 2016). We design an online mechanism that is truthful for both machines and jobs, achieving a competitive ratio of $O(\log m)$. This is the first non-trivial two-sided truthful mechanism for online load balancing and also the first non-trivial machine-side truthful mechanism. Furthermore, we extend our mechanism to the $\ell_q$ norm variant of load balancing, maintaining two-sided truthfulness with a competitive ratio of $\tilde{O}(m^{\frac{1}{q}(1-\frac{1}{q})})$.