2 citations · 4 across the 7 of their papers we have counts for
7 papers · 1 filter
An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
Chao Xu, Mingdong Yang
Cardinality-constrained diameter partitioning asks for a partition of items into two classes of prescribed sizes that minimizes the larger of the two class diameters. We give a…
The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
Jingyang Zhao, Mingyu Xiao, Chao Xu
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that eac…
Multicritera Cuts and Size-Constrained -cuts in Hypergraphs
Calvin Beideman, Karthekeyan Chandrasekaran, Chao Xu
We address counting and optimization variants of multicriteria global min-cut and size-constrained min--cut in hypergraphs. 1. For an -rank -vertex hypergraph endowed with…
LP Relaxation and Tree Packing for Minimum -cuts
Chandra Chekuri, Kent Quanrud, Chao Xu
Karger used spanning tree packings to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts…
Subset Sum Made Simple
Konstantinos Koiliaris, Chao Xu
Subset Sum is a classical optimization problem taught to undergraduates as an example of an NP-hard problem, which is amenable to dynamic programming, yielding polynomial running t…
A note on approximate strengths of edges in a hypergraph
Chandra Chekuri, Chao Xu
Let be an edge-weighted hypergraph of rank . Kogan and Krauthgamer extended Benczúr and Karger's random sampling scheme for cut sparsification from graphs to hypergrap…