45 papers
This paper initiates the study of minimally tough graphs within the class of weakly chordal graphs by providing complete classifications for several specific subclasses and offering simplified proofs for existing results.
This paper introduces a general framework for "s-of-k" positional games where players score points by claiming at least elements of a winning set, and comprehensively analyzes the resulting scores under both optimal play and pairing-restricted strategies across various regular grid structures.
This paper demonstrates that the robust permutation flowshop problem under budgeted uncertainty can be solved by reducing it to polynomially many nominal instances, thereby establishing polynomial-time solvability for two machines and polynomial-time approximability for any fixed number of machines.
This paper demonstrates that while block encoding the 3D heterogeneous Poisson equation for fracture flow offers exponential memory savings and a runtime advantage over classical methods, the inability to improve the effective condition number through separate preconditioner encoding remains a significant barrier to realizing full quantum advantage.
This paper presents the first multiplicative improvement over the greedy algorithm's approximation ratio for maximizing non-negative monotone submodular functions subject to -matroid intersection constraints, achieving a ratio of approximately $0.819kk$.