{"id":"arxiv/2602.20793","url":"https://arxiv.org/abs/2602.20793","tags":["math.OC","cs.DS"],"score":0,"title":"Implicit Decision Diagrams","domain":"math.OC","source":"arxiv","authors":["Isaac Rudich","Louis-Martin Rousseau"],"reviews":0,"subject":"math.OC","summary":"Decision Diagrams (DDs) have emerged as a powerful tool for discrete optimization, with rapidly growing adoption. DDs are directed acyclic layered graphs; restricted DDs are a generalized greedy heuristic for finding feasible solutions, and relaxed DDs compute combinatorial relaxed bounds. There is substantial theory that leverages DD-based bounding, yet the complexity of constructing the DDs themselves has received little attention. Standard restricted DD construction requires $O(w \\log(w))$ per layer; standard relaxed DD construction requires $O(w^2)$, where $w$ is the width of the DD.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-24","reactions":{}}