Various kinds of optimization problems involve nonlinear functions of binary variables that exhibit a property of diminishing marginal returns. Such a property is known as submodularity. Vast amount of work has been devoted to the problem of submodular optimization. In this thesis, we exploit structural information for several classes of submodular optimization problems. We strive for polynomial time algorithms with improved approximation ratio and strong mixed-integer linear formulations of mixed-integer non-linear programs where the epigraph and hypograph of submodular functions of a specific form appear as a substructure together with other side constraints. In Chapter 2, we develop approximation algorithms for the expected utility knapsack problem. We use the sample average approximation framework to approximate the stochastic problem as a deterministic knapsack-constrained submodular maximization problem, and then use an approximation algorithm to solve the deterministic counterpart. We show that a polynomial number of samples are enough for a deterministic approximation that is close in relative error. Then, exploiting the strict monotonicity of typical utility functions, we present an algorithm that maximizes an increasing submodular function over a knapsack constraint with approximation ratio better than the classical $(1-1/e)$ ratio. In Chapter 3, we present polyhedral results for the expected utility knapsack problem. We study a mixed-integer nonlinear set that is the hypograph of $f(a'x)$ together together with a knapsack constraint. We propose a family of inequalities for the convex hull of the nonlinear set by exploiting both the structure of the submodular function $f(a'x)$ and the knapsack constraint. Effectiveness of the proposed inequalities is shown by computational experiments on expected utility maximization problem with budget constraint using a branch-and-cut framework. In Chapter 4, we study a mixed-integer nonlinear set that is the epigraph of $f(a'x)$ together with a cardinality constraint. This mixed-integer nonlinear set arises as a substructure in various constrained submodular minimization problems. We develop a strong linear formulation of the convex hull of the nonlinear set by exploiting both the submodularity of $f(a'x)$ and the cardinality constraint. We provide a full description of the convex hull of the nonlinear set when the vector a has identical components. We also develop a family of facet-defining inequalities when the vector a has nonidentical components. We demonstrate the effectiveness of the proposed inequalities by solving mean-risk knapsack problems using a branch-and-cut framework.

Decision-making is an essential topic for multi-robot coordination and collaboration and is also the main topic of this thesis. Examples can be found in autonomous driving, environmental monitoring, intelligent transportation, etc. To study this problem, we first use multiple applications as motivating examples and then construct the general formulation and solution for those applications. Finally, we extend our investigation from the fundamental problem formulation to resilient and decentralized versions. All those problems are studied in the combinatorial optimization domain with the help of submodular and matroid optimization techniques. As a motivating example, we use a multi-robot environmental monitoring problem to extract the general formulation of a multi-robot decision-making problem. Consider the problem of deploying multi-agent teams for environmental monitoring in a precision farming application. We want to answer the question of when and where to deploy our robots. This is a typical task allocation problem in multi-robot systems. Using the above problem as an example, we first focus on this decision-making problem, e.g., intermittent deployment problem, in a centralized scenario. Given a predictable agriculture environment, we want to make decisions for robots for this monitoring task. The problem is formulated as a combinatorial submodular optimization with matroid constraints. By utilizing the properties of submodularity, we aim to develop a solution with performance guarantees. This motivating example demonstrates how to use a submodular function and matroids to model and solve decision-making problems in multi-robot systems. Based on this framework, we continue to explore the fundamental decision-making problem in several other directions in multi-robot systems, including the robust decision-making problem. All those problems and solutions are formulated and considered in a centralized scenario. In the second part of this thesis, we switch our focus from centralized to decentralized scenarios. We first investigate a case where the robots in a distributed multi-robot system need to work together to guard the system against worst-case attacks while making decisions. By worst-case attacks, we refer to the case where the system may have up to $K$ sensor failures. To increase resilience, we propose a fully distributed algorithm to guide each robot's action selection when the system is attacked. The proposed algorithm guarantees performance in a worst-case scenario where up to a portion of the robots malfunction due to attacks. Based on this specific task allocation problem in robotics, we then create a unified framework for a more general case in a decentralized scenario, e.g., asynchronous decentralized decision-making problems with matroid and knapsack constraints. Finally, several applications in decentralized scenarios are used to validate the theoretical guaranteed performance in robotics. / Doctor of Philosophy / Robots have been widely used as mobile sensing agents nowadays in various applications. Especially with the help of multi-robot systems and artificial intelligence, our lives have changed dramatically in the last decades. One of the most fundamental questions is how to utilize multi-robot systems to finish tasks successfully. To answer this, we need first to formulate the problem from applications and then find theoretically guaranteed answers to those questions. Meanwhile, the robustness and resilience of the solution also need to be taken care of, as cyber-attacks or system failures can happen everywhere. Motivated by those two main goals, this thesis will first use multiple applications to introduce the thesis's topic. We then provide solutions to those problems in centralized and decentralized scenarios. Meanwhile, to increase the system's ability to handle failures, we need to answer how to improve the robustness and resilience of the proposed solutions. Therefore, the topic of this thesis spread from problem formulation to failure-proof solutions. The result of this thesis can be widely used in multi-robot decision-making applications, including autonomous driving, intelligent transportation, and other cyber-physical systems.

In classical network information theory, information packets are treated as commodities, and the nodes of the network are only allowed to duplicate and forward the packets. The new paradigm of network coding, which was introduced by Ahlswede et al., states that if the nodes are permitted to combine the information packets and forward a function of them, the throughput of the network can dramatically increase. In this dissertation we focused on the design and analysis of low complexity network coding schemes for different topologies of wired and wireless networks. In the first part we studied the routing capacity of wired networks. We provided a description of the routing capacity region in terms of a finite set of linear inequalities. We next used this result to study the routing capacity region of undirected ring networks for two multimessage scenarios. Finally, we used new network coding bounds to prove the optimality of routing schemes in these two scenarios. In the second part, we studied node-constrained line and star networks. We derived the multiple multicast capacity region of node-constrained line networks based on a low complexity binary linear coding scheme. For star networks, we examined the multiple unicast problem and offered a linear coding scheme. Then we made a connection between the network coding in a node-constrained star network and the problem of index coding with side information. In the third part, we studied the linear deterministic model of relay networks (LDRN). We focused on a unicast session and derived a simple capacity-achieving transmission scheme. We obtained our scheme by a connection to the submodular flow problem through the application of tools from matroid theory and submodular optimization theory. We also offered polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme. In the final part, we considered the multicasting problem in an LDRN and proposed a new way to construct a coding scheme. Our construction is based on the notion of flow for a unicast session in the third part of this dissertation. We presented randomized and deterministic polynomial-time versions of our algorithm.