Haoqiang Huang

STOC Conference 2025 Conference Paper

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

• Siu-Wing Cheng
• Haoqiang Huang
• Shuo Zhang 0034

Let τ and σ be two polygonal curves in ℝ d for any fixed d . Suppose that τ and σ have n and m vertices, respectively, and m ≤ n . While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of n c in strongly subquadratic time, for some constant c ∈(0,1). We present a randomized algorithm with running time O ( nm 0.99 log( n /ε)) that approximates the Fréchet distance within a factor of 7+ε, with a success probability at least 1−1/ n 6 . We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ε in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

AAMAS Conference 2025 Conference Paper

Environmental Policies within Cournot Oligopoly

• Liang Shan
• Zhengyang Liu
• Haoqiang Huang
• Zihe Wang

We consider how to effectively regulate environmental policies with clear penalties and rewards, through a game-theoretical point of view. To this end, we use social welfare as the primary metric for evaluation. We demonstrate that the best possible social welfare can be achieved through policies that incorporate both linear taxation and subsidies in a Cournot competition model. To make it constructive, we propose efficient algorithms to find optimal policies in a Cournot competition model. Our work can be seen as the first step towards obtaining the optimal environmental policy through the lens of computation.

SODA Conference 2025 Conference Paper

Fréchet Distance in Subquadratic Time

• Siu-Wing Cheng
• Haoqiang Huang

AAAI Conference 2024 Conference Paper

Cost Minimization for Equilibrium Transition

• Haoqiang Huang
• Zihe Wang
• Zhide Wei
• Jie Zhang

In this paper, we delve into the problem of using monetary incentives to encourage players to shift from an initial Nash equilibrium to a more favorable one within a game. Our main focus revolves around computing the minimum reward required to facilitate this equilibrium transition. The game involves a single row player who possesses m strategies and k column players, each endowed with n strategies. Our findings reveal that determining whether the minimum reward is zero is NP-complete, and computing the minimum reward becomes APX-hard. Nonetheless, we bring some positive news, as this problem can be efficiently handled if either k or n is a fixed constant. Furthermore, we have devised an approximation algorithm with an additive error that runs in polynomial time. Lastly, we explore a specific case wherein the utility functions exhibit single-peaked characteristics, and we successfully demonstrate that the optimal reward can be computed in polynomial time.

SODA Conference 2024 Conference Paper

Solving Fréchet Distance Problems by Algebraic Geometric Methods

• Siu-Wing Cheng
• Haoqiang Huang

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let 𝕏 d m and 𝕏 d k be the spaces of all polygonal curves of m and k vertices in ℝ d, respectively. We assume that k ≤ m. Let be the set of ranges in 𝕏 d m for all possible metric balls of polygonal curves in 𝕏 d k under the Fréchet distance. We prove a nearly optimal bound of O(dk log( km )) on the VC dimension of the range space (𝕏 d m, ), improving on the previous O(d 2 k 2 log( dkm )) upper bound and approaching the current Ω( dk log k ) lower bound. Our upper bound also holds for the weak Fréchet distance. We also obtain exact solutions that are hitherto unknown for the curve simplification, range searching, nearest neighbor search, and distance oracle problems. * Research supported by the Research Grants Council, Hong Kong, China (project no. 16208923).

SODA Conference 2023 Conference Paper

Curve Simplification and Clustering under Fréchet Distance

• Siu-Wing Cheng
• Haoqiang Huang

We present new approximation results on curve simplification and clustering under Fréchet distance. Let T = { t i: i ∈ [ n ]} be polygonal curves in ℝ d of m vertices each. Let ℓ be any integer from [ m ]. We study a generalized curve simplification problem: given error bounds δ i > 0 for i ∈ [ n ], find a curve σ of at most ℓ vertices such that d F (σ, t i ) ≤ δ i for i ∈ [ n ]. We present an algorithm that returns a null output or a curve σ of at most ℓ vertices such that d F (σ, τ i ) < δ i + εδ max for i ∈ [ n ], where δ max = max i ∈[ n ] δ i. If the output is null, there is no curve of at most ℓ vertices within a Frechet distance of δ i from τ i for i ∈ [ n ]. The running time is Õ ( n O (ℓ) · m O (ℓ 2 ) · ( d ℓ/ε) O(d ℓ). This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve τ to another curve σ, where the vertices of σ can be anywhere in ℝ d, so that d F (σ, τ) ≤ (1 + ε)δ and |σ| ≤ (1 + α) · min{| c |: d F (c, τ) ≤ δ} for any given δ > 0 and any fixed α, ε ∈ (0, 1). The running time is Õ ( m O (1/α) · ( d /(αε)) O(d /α) ). By combining our technique with some previous results in the literature, we obtain an approximation algorithm for ( k, ℓ)-median clustering. Given T, it computes a set Σ of k curves, each of ℓ vertices, such that is within a factor 1 + ε of the optimum with probability at least 1 — μ for any given μ, ε ∈ (0, 1). The running time is † The full version of the paper can be accessed at https: //arxiv. org/abs/2207. 07809

TCS Journal 2022 Journal Article

Optimal pricing policy design for selling cost-reducing innovation in Cournot games

• Mengjing Chen
• Haoqiang Huang
• Weiran Shen
• Pingzhong Tang
• Zihe Wang
• Jie Zhang

In a marketplace where a number of firms produce and sell a homogeneous product, an innovator develops cost-cutting manufacturing technology and decides to sell it to various firms in the form of a license for profit. Given the innovator's license pricing policy, each firm independently decides whether to purchase the innovation license and how many products to produce. To put it simply, the firms are then in a Cournot market in which the product price is a decreasing function of the total amount of the product on the market. Both the innovator and the firms are acting out of self-interest and look to maximize their utilities. We consider the problem of designing optimal pricing policies for the innovator. A pricing policy could be in the form of a one-off upfront fee, a per-unit royalty fee, or a hybrid of both. Building upon the results of Segal [1], we first show that in a properly designed pricing policy, it is a strictly dominant strategy for the firms to accept the pricing policy, and that this constitutes the unique Nash equilibrium of the game. For the hybrid-fee policy, we devise an algorithm that computes the optimal price in time O ( n 3 ), where n is the number of firms. For the royalty-fee policy, we show that the problem is captured by convex quadratic programming and can be solved in time O ( n 6 L 2 ), where L is the number of input bits. For the upfront-fee policy, we show the optimal policy problem is NP-complete and we devise an FPTAS algorithm. Moreover, we compare the revenue achievable through the above three pricing policies when all firms are identical.