Siyue Liu

Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid Bases

Categories Combinatorial Optimization, Graphs and Matroids Tags , ,

Let \(M\) be a matroid, let \(\ell:E(M)\to G\) be a labeling of its elements by an abelian group, and let \(F\subseteq G\) be finite. A base is \emph{\(F\)-avoiding} if the label sum of its elements is not in $F$. We prove that, for arbitrary costs, a min-cost \(F\)-avoiding base can be obtained from any min-cost … Read more

A Short Proof of Tight Bounds on the Smallest Support Size of Integer Solutions to Linear Equations

Categories Integer Programming, Other Topics Tags ,

In this note, we study the size of the support of solutions to linear Diophantine equations $Ax=b, ~x\in\Z^n$ where $A\in\Z^{m\times n}, b\in\Z^n$. We give an asymptotically tight upper bound on the smallest support size, parameterized by $\|A\|_\infty$ and $m$, and taken as a worst case over all $b$ such that the above system has a … Read more