Search for: All records

Motivated by the importance of user engagement as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph [Formula: see text] and integers k and b, the maximum anchored k-core problem seeks to find a largest subset of vertices [Formula: see text] that induces a subgraph with at least [Formula: see text] vertices of degree at least k. We introduce a new integer programming (IP) formulation for the maximum anchored k-core problem and conduct a polyhedral study on the polytope of the problem. We show the linear programming relaxation of the proposed IP model is at least as strong as that of a naïve formulation. We also identify facet-defining inequalities of the IP formulation. Furthermore, we develop inequalities and fixing procedures to improve the computational performance of our IP model. We use benchmark instances to compare the computational performance of the IP model with (i) the naïve IP formulation and (ii) two existing heuristic algorithms. Our proposed IP model can optimally solve half of the benchmark instances that cannot be solved to optimality either by the naïve model or the existing heuristic approaches. Funding: This work is funded by the National Science Foundation (NSF) [Grant DMS-2318790] titled AMPS: Novel Combinatorial Optimization Techniques for Smartgrids and Power Networks. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2022.0024 . 

Distributed networked systems form an essential resource for computation and applications ranging from commercial, military, scientific, and research communities. Allocation of resources on a given infrastructure is realized through various mapping systems that are tailored towards specific use cases of the requesting applications. While HPC system requests demand compute resources heavy on processor and memory, cloud applications may demand distributed web services that are composed of networked processing and some memory. All resource requests allocate on the infrastructure with some form of network connectivity. However, during mapping of resources, the features and topology constraints of network components are typically handled indirectly through abstractions of user requests. This paper is on a novel graph representation that enables precise mapping methods for distributed networked systems. The proposed graph representations are demonstrated to allocate specific network components and adjacency requirements of a requested graph on a given infrastructure. Furthermore, we report on application of business policy requirements that resulted in increased utilization and a gradual decrease in idle node count as requests are mapped using our proposed methods. 

This phenomenological study (Moustakas, 1994) explores the mentoring needs of 11 engineering postdoctoral scholars of color with an adaptation of the ideal mentoring model (Zambrana et al., 2015) used as the conceptual framework. A critical theory lens (Morrow & Brown, 1994) is applied to Moustakas’ (1994) four-stage process of phenomenological data analysis to examine the interview data: epoché, horizontalization, imaginative variation, and synthesis. The essence of the phenomenon is engineering postdoctoral scholars of color have primary and secondary mentoring needs pertaining to their immediate career acquisition of a tenure-track faculty position. Primary mentoring needs include expanding professional networks for the tenure-track faculty job search and receiving guidance on work-life balance and enhancing technical skills. Secondary needs consist of refining research directions and research expertise promotion, as well as acquiring political guidance on matters of race/ethnicity in academia. These findings reveal the importance of higher education institutions and postdoctoral supervisors assuming greater responsibility for ensuring postdoctoral scholars receive the mentorship and career support they desire, which may require a systematic change in the postdoctoral training environment. 

Abstract To monitor electrical activity throughout the power grid and mitigate outages, sensors known as phasor measurement units can installed. Due to implementation costs, it is desirable to minimize the number of sensors deployed while ensuring that the grid can be effectively monitored. This optimization problem motivates the graph theoretic power dominating set problem. In this paper, we propose a method for computing minimum power dominating sets via a set cover IP formulation and a novel constraint generation procedure. The set cover problem's constraints correspond to neighborhoods of zero forcing forts; we study their structural properties and show they can be separated with delayed row generation. In addition, we offer several computation enhancements which be be applied to our methodology as well as existing methods. The proposed and existing methods are evaluated in several computational experiments. In many of the larger test instances considered, the proposed method exhibits an order of magnitude runtime performance improvement. 

Abstract The concept of branch decomposition was first introduced by Robertson and Seymour in their proof of the Graph Minors Theorem, and can be seen as a measure of the global connectivity of a graph. Since then, branch decomposition and branchwidth have been used for computationally solving combinatorial optimization problems modeled on graphs and matroids. General branchwidth is the extension of branchwidth to any symmetric submodular function defined over a finite set. General branchwidth encompasses graphic branchwidth, matroidal branchwidth, and rankwidth. A tangle basis is related to a tangle, a notion also introduced by Robertson and Seymour; however, a tangle basis is more constructive in nature. It was shown in [I. V. Hicks. Graphs, branchwidth, and tangles! Oh my!Networks, 45:55‐60, 2005] that a tangle basis of orderkis coextensive to a tangle of orderk. In this paper, we revisit the construction of tangle bases computationally for other branchwidth parameters and show that the tangle basis approach is still competitive for computing optimal branch decompositions for general branchwidth. 

Abstract We present an integer programming model to compute the strong rainbow connection number,src(G), of any simple graphG. We introduce several enhancements to the proposed model, including a fast heuristic, and a variable elimination scheme. Moreover, we present a novel lower bound forsrc(G) which may be of independent research interest. We solve the integer program both directly and using an alternative method based on iterative lower bound improvement, the latter of which we show to be highly effective in practice. To our knowledge, these are the first computational methods for the strong rainbow connection problem. We demonstrate the efficacy of our methods by computing the strong rainbow connection numbers of graphs containing up to 379 vertices. 

Abstract Positive semidefinite (PSD) zero forcing is a dynamic graph process in which an initial subset of vertices are colored and may cause additional vertices to become colored through a set of color changing rules. Subsets which cause all other vertices to become colored are called PSD zero forcing sets; the PSD zero forcing number of a graph is the minimum cardinality attained by its PSD zero forcing sets. The PSD zero forcing number is of particular interest as it bounds solutions for the minimum rank and PSD min rank problems, both popular in linear algebra. This paper introduces blocking sets for PSD zero forcing sets which are used to formulate the first integer program (IP) for computing PSD zero forcing numbers of general graphs. It is shown that facets of the feasible region of this IP's linear relaxation correspond to zero forcing forts which induce connected subgraphs, but that identifying min cardinality connected forts is‐hard in general. Auxiliary IPs used to find these blocking sets are also given, enabling the master IP to be solved via constraint generation. Experiments comparing the proposed methods and existing algorithms are provided demonstrating improved runtime performance, particularly so in dense and sparse graphs.