papers

2026

1. Bicriteria Approximation Algorithms for Demand Matching

   Yuchong Pan, and Michel X. Goemans

   2026

   Abs Bib PDF

   The demand matching problem is a common generalization of the knapsack problem and the b-matching problem, in which integer demands on the edges are present. We present three (α, β)-bicriteria approximation algorithms for the demand matching problem, each of which outputs a subset of edges that violates each vertex capacity by at most βtimes the maximum demand, and whose total weight is at least a constant fraction 1/αof the total weight of an optimal solution of the original instance. In particular, the first algorithm is a combinatorial algorithm inspired by the well-known greedy algorithm of Dantzig for the fractional knapsack problem, which produces a (2, 1)-bicriteria approximation. Indeed, we prove more generally the existence of a (k, 1)-bicrteria approximation algorithm for the k-hypergraph demand matching problem, which includes the demand matching problem when k = 2. The second algorithm uses the iterative relaxation technique of Jain and a structural lemma of an extreme point of the natural LP relaxation of the demand matching problem, and produces a (3/2, 1)-bicriteria approximation. The third algorithm takes the better of two rounding strategies in the iterative relaxation framework when an odd cycle is present, and yields a (4/3, 1)-bicriteria approximation. The weight guarantees of all three approximation algorithms are with respect to the optimal value of the natural LP relaxation, where for the third algorithm we assume that the demand of each edge is at most the capacity of each of its endpoints.

   @unpublished{pan2026bicriteria,
     title = {Bicriteria Approximation Algorithms for Demand Matching},
     author = {Pan, Yuchong and Goemans, Michel X.},
     year = {2026},
   }

2025

1. SIDMA

   

   Planarity via Spanning Tree Number: A Linear-Algebraic Criterion

   Alan Bu, and Yuchong Pan

   SIAM J. Discrete Math., 2025

   Abs Bib PDF Poster Slides

   We introduce a novel linear-algebraic planarity criterion based on the number of spanning trees. We call a matrix an incidence submatrix if each row has at most one 1, at most one -1, and all other entries zero. Given a connected graph G with m edges, we consider the maximum determinant \mathsf{maxdet}(G) of an m \times m matrix [M|N], where M is the incidence matrix of G with one column removed, over all incidence submatrices N of appropriate size, and define its excess to be the number of spanning trees in G minus \mathsf{maxdet}(G). Given a disconnected graph, we define its excess to be the sum of the excesses of its connected components. We show that the excess of a graph is 0 if it is planar, and at least 18 otherwise. This provides a “certificate of planarity” of a planar graph that can be verified by computing the determinant of a sparse matrix and counting spanning trees. Furthermore, we derive an upper bound on the maximum determinant of an m \times m matrix [M|N], where M and N are incidence submatrices. Motivated by this bound and numerical evidence, we conjecture that this maximum determinant is equal to the maximum number of spanning trees in a planar graph with m edges. We present partial progress towards this conjecture. In particular, we prove that the \mathsf{maxdet}(⋅) value of any subdivision of K_{3, 3} or K_5 is at most that of the best planar graph with the same number of edges.

   @article{bu2025planarity,
     title = {Planarity via Spanning Tree Number: A Linear-Algebraic Criterion},
     author = {Bu, Alan and Pan, Yuchong},
     journal = {SIAM J. Discrete Math.},
     publisher = {Society for Industrial and Applied Mathematics},
     volume = {39},
     number = {2},
     pages = {728-751},
     year = {2025},
     doi = {10.1137/24M1660395},
     url = {https://doi.org/10.1137/24M1660395},
   }

2024

1. 

   On High-Value and High-Flow Cycles at Basic Feasible Solutions of the Subtour Elimination Relaxations for the Symmetric and Asymmetric Traveling Salesman Problems

   Michel X. Goemans, and Yuchong Pan

   2024

   Abs Bib

   Melkonian [Inf. Process. Lett., 101 (2007)] introduced the concepts of high-value and high-flow cycles at basic feasible solutions of the subtour elimination relaxation for the asymmetric traveling salesman problem (ATSP), in hope of designing a constant-factor approximation algorithm for ATSP. We show that high-value cycles do not always exist at basic feasible solutions of the subtour elimination relaxations for the symmetric and asymmetric traveling salesman problems. Furthermore, we exhibit a reduction from the thin tree conjecture to the existence of a constant-flow cycle, the former of which is at least as hard as finding a constant-factor approximation algorithm for ATSP itself.

   @unpublished{goemans2024high,
     title = {On High-Value and High-Flow Cycles at Basic Feasible Solutions of the Subtour Elimination Relaxations for the Symmetric and Asymmetric Traveling Salesman Problems},
     author = {Goemans, Michel X. and Pan, Yuchong},
     year = {2024},
   }

2023

1. 

   A Counterexample to Box-Half-Integrality of the Intersection of Crossing Submodular Flow Systems

   Michel X. Goemans, and Yuchong Pan

   2023

   Abs Bib PDF

   Abdi, Cornuéjols and Zambelli proved that the intersection of two crossing submodular flow systems on a weakly connected digraph is totally dual integral, but not box-integral. Abdi conjectured that this polyhedral system is box-half-integral. We exhibit a counterexample to their conjecture.

   @unpublished{goemans2023counterexample,
     title = {A Counterexample to Box-Half-Integrality of the Intersection of Crossing Submodular Flow Systems},
     author = {Goemans, Michel X. and Pan, Yuchong},
     year = {2023},
   }

2021

1. 

   Optimization Problems on Network Flows with Degree Constraints

   Yuchong Pan

   2021

   Abs Bib PDF

   In a vertex-capacitated directed graph with sources and sinks, we would like to concurrently route demands from the sources to the sinks. This model has many applications in the real world. However, conditions in the reality usually incur new side constraints to this general model. For instance, the next-hop routing in Internet protocol (IP) networks requires each router to have one single next destination, called the next hop, for each incoming packet destined to an IP address. A flow with this property is said to be confluent. If this constraint is relaxed to allow d next destinations at each vertex, then such a flow is said to be d-furcated. In general, side constraints concerning bounded out-degree of each vertex give rise to network flows with degree constraints. Such constraints contribute to simplicity of resulting network flow models. Given a network flow model, several optimization problems can be asked. For instance, how the demands can be routed so that the flow does not exceed the capacity at each vertex too much? Another natural question is to find a subset of the demands with the maximum amount which can be routed subject to the vertex capacities. In this thesis, we survey algorithms that find approximate solutions close to optimum values within theoretically guaranteed factors.

   @masterthesis{pan2021optimization,
     title = {Optimization Problems on Network Flows with Degree Constraints},
     author = {Pan, Yuchong},
     year = {2021},
     type = {Undergraduate Honours Thesis},
     school = {University of British Columbia},
   }