More Like this

1. Tree embeddings for hop-constrained network design

   https://doi.org/10.1145/3406325.3451053  

   Haeupler, Bernhard; Hershkowitz, D. Ellis; Zuzic, Goran (June 2021, Symposium on Theory of Computing (STOC))

   null (Ed.)

   Network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less well understood than their hop-unconstrained counterparts. A significant algorithmic barrier in this setting is the fact that hop-constrained distances in graphs are very far from being a metric. We show that, nonetheless, hop-constrained distances can be approximated by distributions over ``partial tree metrics.'' We build this result into a powerful and versatile algorithmic tool which, similarly to classic probabilistic tree embeddings, reduces hop-constrained problems in general graphs to hop-unconstrained problems on trees. We then use this tool to give the first poly-logarithmic bicriteria approximations for the hop-constrained variants of many classic network design problems. These include Steiner forest, group Steiner tree, group Steiner forest, buy-at-bulk network design as well as online and oblivious versions of many of these problems. 

   more » « less
2. Hindsight learning for MDPs with exogenous inputs

   Sinclair, Sean_R; Frujeri, Felipe; Cheng, Ching-An; Marshall, Luke; Barbalho, Hugo; Li, Jingling; Neville, Jennifer; Menache, Ishai; Swaminathan, Adith (July 2023, Proceedings of Machine Learning Research)

   Many resource management problems require sequential decision-making under uncertainty, where the only uncertainty affecting the decision outcomes are exogenous variables outside the control of the decision-maker. We model these problems as Exo-MDPs (Markov Decision Processes with Exogenous Inputs) and design a class of data-efficient algorithms for them termed Hindsight Learning (HL). Our HL algorithms achieve data efficiency by leveraging a key insight: having samples of the exogenous variables, past decisions can be revisited in hindsight to infer counterfactual consequences that can accelerate policy improvements. We compare HL against classic baselines in the multi-secretary and airline revenue management problems. We also scale our algorithms to a business-critical cloud resource management problem – allocating Virtual Machines (VMs) to physical machines, and simulate their performance with real datasets from a large public cloud provider. We find that HL algorithms outperform domain-specific heuristics, as well as state-of-the-art reinforcement learning methods. 

   more » « less
3. Bag Query Containment and Information Theory

   https://doi.org/10.1145/3472391  

   Khamis, Mahmoud Abo; Kolaitis, Phokion G.; Ngo, Hung Q.; Suciu, Dan (September 2021, ACM Transactions on Database Systems)

   The query containment problem is a fundamental algorithmic problem in data management. While this problem is well understood under set semantics, it is by far less understood under bag semantics. In particular, it is a long-standing open question whether or not the conjunctive query containment problem under bag semantics is decidable. We unveil tight connections between information theory and the conjunctive query containment under bag semantics. These connections are established using information inequalities, which are considered to be the laws of information theory. Our first main result asserts that deciding the validity of a generalization of information inequalities is many-one equivalent to the restricted case of conjunctive query containment in which the containing query is acyclic; thus, either both these problems are decidable or both are undecidable. Our second main result identifies a new decidable case of the conjunctive query containment problem under bag semantics. Specifically, we give an exponential-time algorithm for conjunctive query containment under bag semantics, provided the containing query is chordal and admits a simple junction tree. 

   more » « less
4. Bag Query Containment and Information Theory

   https://doi.org/10.1145/3375395.3387645  

   Abo Khamis, Mahmoud; Kolaitis, Phokion G.; Ngo, Hung Q.; Suciu, Dan (June 2020, PODS)

   The query containment problem is a fundamental algorithmic prob- lem in data management. While this problem is well understood under set semantics, it is by far less understood under bag semantics. In particular, it is a long-standing open question whether or not the conjunctive query containment problem under bag semantics is decidable. We unveil tight connections between information theory and the conjunctive query containment under bag semantics. These connections are established using information inequalities, which are considered to be the laws of information theory. Our first main result asserts that deciding the validity of a generalization of infor- mation inequalities is many-one equivalent to the restricted case of conjunctive query containment in which the containing query is acyclic; thus, either both these problems are decidable or both are undecidable. Our second main result identifies a new decidable case of the conjunctive query containment problem under bag semantics. Specifically, we give an exponential time algorithm for conjunctive query containment under bag semantics, provided the containing query is chordal and admits a simple junction tree. 

   more » « less
5. The Benefits and Limits of Urban Tree Planting for Environmental and Human Health

   https://doi.org/10.3389/fevo.2021.603757  

   Pataki, Diane E.; Alberti, Marina; Cadenasso, Mary L.; Felson, Alexander J.; McDonnell, Mark J.; Pincetl, Stephanie; Pouyat, Richard V.; Setälä, Heikki; Whitlow, Thomas H. (April 2021, Frontiers in Ecology and Evolution)

   null (Ed.)

   Many of the world’s major cities have implemented tree planting programs based on assumed environmental and social benefits of urban forests. Recent studies have increasingly tested these assumptions and provide empirical evidence for the contributions of tree planting programs, as well as their feasibility and limits, for solving or mitigating urban environmental and social issues. We propose that current evidence supports local cooling, stormwater absorption, and health benefits of urban trees for local residents. However, the potential for urban trees to appreciably mitigate greenhouse gas emissions and air pollution over a wide array of sites and environmental conditions is limited. Consequently, urban trees appear to be more promising for climate and pollution adaptation strategies than mitigation strategies. In large part, this is due to space constraints limiting the extent of urban tree canopies relative to the current magnitude of emissions. The most promising environmental and health impacts of urban trees are those that can be realized with well-stewarded tree planting and localized design interventions at site to municipal scales. Tree planting at these scales has documented benefits on local climate and health, which can be maximized through targeted site design followed by monitoring, adaptive management, and studies of long-term eco-evolutionary dynamics. 

   more » « less