It came to my attention that Problem 2 had been studied under the name of "isotonic regression". Sec 5 of my paper essentially rediscovers an algorithm in Stanislav Angelov, Boulos Harb, Sampath Kannan, Li-San Wang: Weighted isotonic regression under the L1 norm. SODA 2006: 783-791. When the dimensionality d is a constant, the following paper presented an algorithm of time O(n^{1.5} log^{d+1} n) Quentin F. Stout: Isotonic Regression for Multiple Independent Variables. Algorithmica 71(2): 450-470 (2015). Recently, the running time has been improved to o(n^{1.5}) in Quentin F. Stout: L0 Isotonic Regression With Secondary Objectives. ArXiv 2106.00279 (2021). ===== All my results on Problem 1 are new to the best of my knowledge.