24 citations · 38 across the 14 of their papers we have counts for
15 papers
Sharp Bounds on the Number of Small Cuts
Chao Xu, Mingdong Yang
Let be the minimum cut value of an -vertex undirected multigraph. For every fixed , we prove that there are cuts of size strictly below .…
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…
On the Congruency-Constrained Matroid Base
Siyue Liu, Chao Xu
Consider a matroid where all elements are labeled with an element in . We are interested in finding a base where the sum of the labels is congruent to . We s…
Almost optimum -covering of
Ke Shi, Chao Xu
A subset of the ring is referred to as a -covering set if . We show that there exists a -…
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…
Global and fixed-terminal cuts in digraphs
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +2
The computational complexity of multicut-like problems may vary significantly depending on whether the terminals are fixed or not. In this work we present a comprehensive study of…
Computing minimum cuts in hypergraphs
Chandra Chekuri, Chao Xu
We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph with , and the best known algor…
A Faster Pseudopolynomial Time Algorithm for Subset Sum
Konstantinos Koiliaris, Chao Xu
Given a multiset of positive integers and a target integer , the subset sum problem is to decide if there is a subset of that sums up to . We present a new divide…
Marking Streets to Improve Parking Density
Chao Xu, Steven Skiena
Street parking spots for automobiles are a scarce commodity in most urban environments. The heterogeneity of car sizes makes it inefficient to rigidly define fixed-sized spots. Ins…
Dealing With 4-Variables by Resolution: An Improved MaxSAT Algorithm
Jianer Chen, Chao Xu
We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolu…
Detecting Weakly Simple Polygons
Hsien-Chih Chang, Jeff Erickson, Chao Xu
A closed curve in the plane is weakly simple if it is the limit (in the Fréchet metric) of a sequence of simple closed curves. We describe an algorithm to determine whether a close…