An official website of the United States government
We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems, namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph [Formula: see text] with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k nonempty parts [Formula: see text]—known as a k-partition—so as to minimize an objective of interest. (1) If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. (2) If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an [Formula: see text]-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known [Formula: see text]-time deterministic algorithm, in which n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs). Funding: All authors were supported by NSF AF 1814613 and 1907937.
more »
« less
Background results for robust minmax control of linear dynamical systems
The purpose of this note is to summarize the arguments required to derive the results appearing in robust minmax control of linear dynamical systems using a quadratic stage cost. The main results required in robust minmax control are Corollary 19 and Proposition 20. Moreover, the solution to the trust-region problem given in Proposition 15 and Lemma 16 may be of more general interest.
more »
« less
- Award ID(s):
- 2027091
- PAR ID:
- 10545403
- Publisher / Repository:
- ArXiv
- Date Published:
- Edition / Version:
- http://arxiv.org/abs/2406.15682
- Format(s):
- Medium: X
- Institution:
- University of California, Santa Barbara
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper introduces the concept of leakage-robust Bayesian persuasion. Situated between public Bayesian persuasion and private Bayesian persuasion, leakage-robust persuasion considers a setting where one or more signals privately communicated by a sender to the receivers may be leaked. We study the design of leakage-robust Bayesian persuasion schemes and quantify the price of robustness using two formalisms: - The first notion, k-worst-case persuasiveness, requires a signaling scheme to remain persuasive as long as each receiver observes no more than k leaked signals from other receivers. We quantify the Price of Robust Persuasiveness (PoRPk)— i.e., the gap in sender's utility as compared to the optimal private persuasion scheme—as Θ(min{2k,n}) for supermodular sender utilities and Θ(k) for submodular or XOS sender utilities, where n is the number of receivers. This result also establishes that in some instances, Θ(log k) leakages are sufficient for the utility of the optimal leakage-robust persuasion to degenerate to that of public persuasion. - The second notion, expected downstream utility robustness, relaxes the persuasiveness requirement and instead considers the impact on sender's utility resulting from receivers best responding to their observations. By quantifying the Price of Robust Downstream Utility (PoRU) as the gap between the sender's expected utility over the randomness in the leakage pattern as compared to private persuasion, our results show that, over several natural and structured distributions of leakage patterns, PoRU improves PoRP to Θ(k) or even Θ(1), where k is the maximum number of leaked signals observable to each receiver across leakage patterns in the distribution. En route to these results, we show that subsampling and masking serve as general-purpose algorithmic paradigms for transforming any private persuasion signaling scheme to one that is leakage-robust, with minmax optimal loss in sender's utility. A full version of this paper can be found at https://arxiv.org/abs/2411.16624.more » « less
-
Summary Scenario‐based model predictive control (MPC) methods can mitigate the conservativeness inherent to open‐loop robust MPC. Yet, the scenarios are often generated offline based on worst‐case uncertainty descriptions obtaineda priori, which can in turn limit the improvements in the robust control performance. To this end, this paper presents a learning‐based, adaptive‐scenario‐tree model predictive control approach for uncertain nonlinear systems with time‐varying and/or hard‐to‐model dynamics. Bayesian neural networks (BNNs) are used to learn a state‐ and input‐dependent description of model uncertainty, namely the mismatch between a nominal (physics‐based or data‐driven) model of a system and its actual dynamics. We first present a new approach for training robust BNNs (RBNNs) using probabilistic Lipschitz bounds to provide a less conservative uncertainty quantification. Then, we present an approach to evaluate the credible intervals of RBNN predictions and determine the number of samples required for estimating the credible intervals given a credible level. The performance of RBNNs is evaluated with respect to that of standard BNNs and Gaussian process (GP) as a basis of comparison. The RBNN description of plant‐model mismatch with verified accurate credible intervals is employed to generate adaptive scenarios online for scenario‐based MPC (sMPC). The proposed sMPC approach with adaptive scenario tree can improve the robust control performance with respect to sMPC with a fixed, worst‐case scenario tree and with respect to an adaptive‐scenario‐based MPC (asMPC) using GP regression on a cold atmospheric plasma system. Furthermore, closed‐loop simulation results illustrate that robust model uncertainty learning via RBNNs can enhance the probability of constraint satisfaction of asMPC.more » « less
-
Ribeiro, Haroldo V. (Ed.)We examine patterns of reported crime in Santa Monica, California before and after the passage of Proposition 47, a 2014 initiative that reclassified some non-violent felonies as misdemeanors. We also investigate impacts of the opening of four new light rail stations in 2016 and of increased community-based policing starting in late 2018. Our statistical analyses of reclassified crimes—larceny, fraud, possession of narcotics, forgery, receiving/possessing stolen property—and non-reclassified ones are based on publicly available reported crime data from 2006 to 2019. These analyses examine reported crime at various levels: city-wide, within eight neighborhoods, and within a 450-meter radius of the new transit stations. Monthly reported reclassified crimes increased city-wide by approximately 15% after enactment of Proposition 47, with a significant drop observed in late 2018. Downtown exhibited the largest overall surge. Reported non-reclassified crimes fell overall by approximately 9%. Areas surrounding two new train stations, including Downtown, saw significant increases in reported crime after train service began. While reported reclassified crimes increased after passage of Proposition 47, non-reclassified crimes, for the most part, decreased or stayed constant, suggesting that Proposition 47 may have impacted reported crime in Santa Monica. Reported crimes decreased in late 2018 concurrent with the adoption of new community-based policing measures. Follow-up studies needed to confirm long-term trends may be challenging due to the COVID-19 pandemic that drastically changed societal conditions. While our research detects changes in reported crime, it does not provide causative explanations. Our work, along with other considerations relevant to public utility, respect for human rights, and existence of socioeconomic disparities, may be useful to law enforcement and policymakers to assess the overall effect of Proposition 47.more » « less
-
The challenge of failure management emerges in decentralized architectures due to the distributed nature of the layered control process. Failures in microgrid system may occur at the microgrid level or any of the control layers. A failure detection and response mechanism is required to attain a reliable, fault-tolerant microgrid operation. This paper introduces a Failure Management Unit as an essential function in a microgrid Energy Management System. The proposed unit comprises failure detection mechanisms and a recovery algorithm. The proposed system is applied to a microgrid case study and shows a robust detection and recovery outcome during a system failure. The real-time experimental results were achieved using Hardware-In-the-Loop platform. Coordination between controllers during the recovery period requires low-bandwidth communications, which has no significant overhead on the communication infrastructure.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Posted Content:
- The DOI is not currently available.
