2 citations · 4 across the 3 of their papers we have counts for
6 papers
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…
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…