transportation planners

Abstract: Strong Connectivity Augmentation (SCA) asks whether a directed acyclic graph can be made strongly connected by adding at most $k$ prescribed links whose total weight is within a given budget. Klinkby, Misra, and Saurabh (SODA 2021) gave an $O^*(2^{O(k\log k)})$-time algorithm and asked whether the problem admits a single-exponential parameterized algorithm and a polynomial kernel. We answer both questions affirmatively: SCA can be solved in $O^*(9^k)$ time and admits a polynomial kernel with $O(k^4)$ vertices and $O(k^{16})$ bits. For unweighted SCA, we obtain $O^*(4^k)$ time and a kernel with $O(k^3)$ vertices. Our algorithms are based on a particularly simple reduction to Strongly Connected Spanning Subgraph with two edge costs.

Abstract: We introduce cooperative integer programming games (CIPGs), in which agents pool budget constraints to accomplish indivisible tasks jointly and the characteristic function maps every coalition to the optimal value of a pooled integer program. Our goal is to identify an optimal coalition structure (OCS) and a stable one (OSCS). We derive a stability inequality that keeps each formed coalition in the Core with respect to itself, and present two mixed-integer OCS formulations, aggregated and disaggregated, proving that the disaggregated formulation is integer-equivalent yet yields a tighter LP relaxation. Building on the stability inequality we develop lifted stability cuts, several separation strategies inside a cutting-plane algorithm, an SCS-feasible primal heuristic that constructs warm starts with guaranteed stability, and a payoff-refinement step computing the Shapley value and the nucleolus of every formed coalition. On benchmark cooperative knapsack games, the method certifies optimality with up to 16 players and reaches MIP gaps below 1% at 30 players while evaluating 766 of the roughly $10^9$ coalition values.

Abstract: Travel survey data are essential for transportation planning and travel behavior analysis, yet collecting large-scale representative samples is costly and time-consuming. A practical alternative is to generate synthetic survey records from a few-shot sample. However, such samples provide incomplete coverage of heterogeneous traveler groups and insufficient evidence for recovering the complex dependencies between demographic characteristics and travel behavior. Existing approaches have complementary limitations. Probabilistic generative models such as Bayesian networks (BNs) offer explicit distributional control, but structures learned from few-shot samples may omit meaningful dependencies or retain spurious ones. Large language models (LLMs) can help address these difficulties in BN structure learning by providing behavioral knowledge that complements the limited statistical evidence. We therefore propose LEBGen, an LLM-enhanced BN framework that uses this knowledge to refine network structure for few-shot travel survey data generation. Specifically, the LLM first identifies traveler personas from demographic attribute and travel behavior statistics, then recovers dependencies missed by the persona-augmented BN structure and prune spurious ones. The refined BN is parameterized exclusively from the observed data to generate synthetic records. Under a 2% few-shot setting on the 2022 Hong Kong Travel Characteristics Survey, LEBGen reduces the mean marginal Jensen-Shannon divergence from 0.0671 to 0.0091 and the mean absolute Cramer's V error by 14.3% over the best-performing baseline, substantially improving both distributional and dependency fidelity.