With an increasing number of satellites in orbit, consensus across a heterogeneous group of satellites can lead to a more neutral, unbiased, and accurate decisions. Fault tolerant consensus algorithms such as Practical Byzantine Fault Tolerance (pBFT) require communication with all other network members up to 4 times. In a network with thousands of satellites in space on different trajectories, this time can approach millennia. There-fore, identifying a subset of satellites that can form a sub-network able to converge to a consensus decision in a useful time window, while maximising the number of members to increase consensus accuracy and trustworthiness, can be formulated as a multi-objective combinatorial optimisation problem. The problem is explained and defined with the optimisation method and the consensus algorithm steps described. Metrics for measuring the output of the optimal pareto front are considered and applied to the front computed. The real satellite positions used generate a non-fixed topology and high latency scenario such as that of a real on-orbit decision being made. The trend shown over 100 days of satellite positions propagation with up to 82 International Charter: Space and Major Disasters satellites shows up to 22 satellites can be used in a subset with a near linear increase in consensus time along the optimal pareto front and exponential trend for the mean values computed over 100 runs of the NSGA-II algorithm. The minimum consensus time is found to be 47 minutes for a subset of 4 satellites for the given time frame.

Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is Strongly Controllable (SC) there exists a concrete schedule that is robust to any uncertainty. We solve the problem of determining Chance Constrained PSTN SC as a Joint Chance Constrained optimisation problem via column generation, lifting the usual assumptions of independence and Boole's inequality typically leveraged in PSTN literature. Our approach offers on average a 10 times reduction in cost versus previous methods.

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $$G= (A\, \dot{\cup }\, P, E)$$ with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (WMLQ), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of WMLQ from the viewpoints of classical polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between $$\textsf {NP}$$ -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $$u_{\max }$$ as basis, and we prove that this dependence is necessary unless $$\textsf {FPT}= \textsf {W}[1]$$ . The approximability of WMLQ is also discussed: we present an approximation algorithm for the general case with performance guarantee $$u_{\max }+1$$ , which is asymptotically best possible unless $$\textsf {P}= \textsf {NP}$$ . Finally, we elaborate on how most of our positive results carry over to matchings in arbitrary graphs with lower quotas.

We study a problem that integrates buy-at-bulk network design into the classical facility location problem. We consider a generalization of the facility location problem where multiple clients may share a capacitated network to connect to open facilities instead of requiring direct links. In this problem, we wish to open facilities, build a routing network by installing access cables of different costs and capacities, and route every client demand to an open facility. We provide a path-based formulation and we compare it with the natural compact formulation for this problem. We then design an exact branch-price-and-cut algorithm for solving the path-based formulation. We study the effect of two families of valid inequalities. In addition to this, we present three different types of primal heuristics and employ a hybrid approach to effectively combine these heuristics in order to improve the primal bounds. We finally report the results of our approach that were tested on a set of real world instances, as well as two sets of benchmark instances and evaluate the effects of our valid inequalities and primal heuristics.

We study a natural generalization of the maximum weight many-to-one matching problem. We are given an undirected bipartite graph $$G= (A \dot{\cup }P, E)$$ with weights on the edges in E, and with lower and upper quotas on the vertices in P. We seek a maximum weight many-to-one matching satisfying two sets of constraints: vertices in A are incident to at most one matching edge, while vertices in P are either unmatched or they are incident to a number of matching edges between their lower and upper quota. This problem, which we call maximum weight many-to-one matching with lower and upper quotas (wmlq), has applications to the assignment of students to projects within university courses, where there are constraints on the minimum and maximum numbers of students that must be assigned to each project. In this paper, we provide a comprehensive analysis of the complexity of wmlq from the viewpoints of classic polynomial time algorithms, fixed-parameter tractability, as well as approximability. We draw the line between $$\mathsf{NP}$$ -hard and polynomially tractable instances in terms of degree and quota constraints and provide efficient algorithms to solve the tractable ones. We further show that the problem can be solved in polynomial time for instances with bounded treewidth; however, the corresponding runtime is exponential in the treewidth with the maximum upper quota $$u_{\max }$$ as basis, and we prove that this dependence is necessary unless $$\mathsf{FPT}= \mathsf{W}[1]$$ . Finally, we also present an approximation algorithm for the general case with performance guarantee $$u_{\max }+1$$ , which is asymptotically best possible unless $$\mathsf{P}= \mathsf{NP}$$ .

Flows over time are used to model many real‐world logistic and routing problems. The networks underlying such problems—streets, tracks, etc.—are inherently undirected and directions are only imposed on them to reduce the danger of colliding vehicles and similar problems. Thus, the question arises, what influence the orientation of the network has on the network flow over time problem that is being solved on the oriented network. In the literature, this is also referred to as the contraflow or lane reversal problem. We introduce and analyze the price of orientation: How much flow is lost in any orientation of the network if the time horizon remains fixed? We prove that there is always an orientation where we can still send one‐third of the flow and this bound is tight. For the special case of networks with a single source or sink, this fraction is half, which is again tight. We present more results of similar flavor and also show nonapproximability results for finding the best orientation for single and multicommodity maximum flows over time. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 196–209 2015

We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem (UFLP) and seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. We say that a sequence has a competitive ratio of k, if the cost of serving the first ℓ customers in the sequence is at most k times the optimal solution for serving any ℓ customers for all possible values of ℓ. We provide an incremental framework that computes a sequence with a competitive ratio of at most eight and a worst‐case instance that provides a lower bound of three for any incremental sequence. We also present the results of our computational experiments carried out on a set of benchmark instances for the UFLP. The problem has applications in multistage network planning. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 306–311 2015

The cost of post-secondary education in the U.S. continues to grow faster than salaries and inflation. In fact, the real cost of a college education has climbed almost 30 in the past 10 years and shows no sign of stabilizing in the near future. The economic competitiveness of the country increasingly depends on a skilled workforce with a post-secondary education capable of dealing with the demands of the global market. Thus, college attainment is at the center of producing a skilled workforce, and so it is, post-secondary education affordability. Using the national post-secondary student aid surveyor the year 2003- 2004, which is representative of the entire undergraduate population in the U.S., this study examines the various ways students and families pay for post-secondary education and its subsequent effect on persistence and performance for all groups of students across racial/ethnic and social-economic status lines.We use a spectral clustering algorithm based on normalized cuts to classify students based on their similarities. More specifically, we construct a social network with the students as the nodes of the graph and edge between pair of the students is weighted based on their similarity in attributes. We then obtain three nontrivial smallest of the Laplacian matrix. We use these to perform a k-means clustering in the eigenspace. We were able to establish meaningful clusters by this approach that helps in classifying students based on the relation between their persistence level and conditions of living.

Social network analysis deals with the interactions between individuals by considering them as nodes of a network (graph) whereas their relations are mapped as network edges. Study of such structures lies on the intersection of two different areas of research: sociology and graph theory. In this paper we give an overview of the mathematical concepts used for studying these networks as well as the major methodologies employed for the study of them. Most prominent applications and dominant research trends of the field are also discussed.