Certain graphs can be described by the distribution of the edges in its subgraphs. For example, a cycle C is a graph that satisfies |E(H)| |V (H)| < |E(C)| |V (C)| = 1 for all non-trivial subgraphs of C. Similarly, a tree T is a graph that satisfies |E(H)| |V (H)|−1 ≤ |E(T)| |V (T)|−1 = 1 for all non-trivial subgraphs of T. In general, a balanced graph G is a graph such that |E(H)| |V (H)| ≤ |E(G)| |V (G)| and a 1-balanced graph is a graph such that |E(H)| |V (H)|−1 ≤ |E(G)| |V (G)|−1 for all non-trivial subgraphs of G. Apart from these, for integers k and l, graphs G that satisfy the property |E(H)| ≤ k|V (H)| − l for all non-trivial subgraphs H of G play important roles in defining rigid structures. This dissertation is a formal study of a class of density functions that extends the above mentioned ideas. For a rational number r ≤ 1, a graph G is said to be r-balanced if and only if for each non-trivial subgraph H of G, we have |E(H)| |V (H)|−r ≤ |E(G)| |V (G)|−r . For r > 1, similar definitions are given. Weaker forms of r-balanced graphs are defined and the existence of these graphs is discussed. We also define a class of vulnerability measures on graphs similar to the edge-connectivity of graphs and show how it is related to r-balanced graphs. All these definitions are matroidal and the definitions of r-balanced matroids naturally extend the definitions of r-balanced graphs. The vulnerability measures in graphs that we define are ranked and are lesser than the edge-connectivity. Due to the relationship of the r-balanced graphs with the vulnerability measures defined in the dissertation, identifying r-balanced graphs and calculating the vulnerability measures in graphs prove to be useful in the area of network survivability. Relationships between the various classes of r-balanced matroids and their weak forms are discussed. For r ∈ {0, 1}, we give a method to construct big r-balanced graphs from small r-balanced graphs. This construction is a generalization of the construction of Cartesian product of two graphs. We present an algorithmic solution of the problem of transforming any given graph into a 1-balanced graph on the same number of vertices and edges as the given graph. This result is extended to a density function defined on the power set of any set E via a pair of matroid rank functions defined on the power set of E. Many interesting results may be derived in the future by choosing suitable pairs of matroid rank functions and applying the above result.

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.

Thesis (M.Sc.). / Title from title page of PDF (viewed 2008/01/30). Written for the School of Computer Science. Includes bibliographical references.

Standard local search algorithms for combinatorial optimization problems repeatedly apply small changes to a current solution to improve the problem's given objective function. In contrast, non-oblivious local search algorithms are guided by an auxiliary potential function, which is distinct from the problem's objective. In this thesis, we compare the standard and non-oblivious approaches for a variety of problems, and derive new, improved non-oblivious local search algorithms for several problems in the area of constrained linear and monotone submodular maximization. First, we give a new, randomized approximation algorithm for maximizing a monotone submodular function subject to a matroid constraint. Our algorithm's approximation ratio matches both the known hardness of approximation bounds for the problem and the performance of the recent ``continuous greedy'' algorithm. Unlike the continuous greedy algorithm, our algorithm is straightforward and combinatorial. In the case that the monotone submodular function is a coverage function, we can obtain a further simplified, deterministic algorithm with improved running time. Moving beyond the case of single matroid constraints, we then consider general classes of set systems that capture problems that can be approximated well. While previous such classes have focused primarily on greedy algorithms, we give a new class that captures problems amenable to optimization by local search algorithms. We show that several combinatorial optimization problems can be placed in this class, and give a non-oblivious local search algorithm that delivers improved approximations for a variety of specific problems. In contrast, we show that standard local search algorithms give no improvement over known approximation results for these problems, even when allowed to search larger neighborhoods than their non-oblivious counterparts. Finally, we expand on these results by considering standard local search algorithms for constraint satisfaction problems. We develop conditions under which the approximation ratio of standard local search remains limited even for super-polynomial or exponential local neighborhoods. In the special case of MaxCut, we further show that a variety of techniques including random or greedy initialization, large neighborhoods, and best-improvement pivot rules cannot improve the approximation performance of standard local search.

In this thesis we consider two combinatorial optimization problems that relate to the field of persistent monitoring. In the first part, we extend the classic problem of finding the maximum weight Hamiltonian cycle in a graph to the case where the objective is a submodular function of the edges. We consider a greedy algorithm and a 2-matching based algorithm, and we show that they have approximation factors of 1/2+κ and max{2/(3(2+κ)),(2/3)(1-κ)} respectively, where κ is the curvature of the submodular function. Both algorithms require a number of calls to the submodular function that is cubic to the number of vertices in the graph. We then present a method to solve a multi-objective optimization consisting of both additive edge costs and submodular edge rewards. We provide simulation results to empirically evaluate the performance of the algorithms. Finally, we demonstrate an application in monitoring an environment using an autonomous mobile sensor, where the sensing reward is related to the entropy reduction of a given a set of measurements. In the second part, we study the problem of selecting sensors to obtain the most accurate state estimate of a linear system. The estimator is taken to be a Kalman filter and we attempt to optimize the a posteriori error covariance. For a finite time horizon, we show that, under certain restrictive conditions, the problem can be phrased as a submodular function optimization and that a greedy approach yields a 1-1/(e^(1-1/e))-approximation. Next, for an infinite time horizon, we characterize the exact conditions for the existence of a schedule with bounded estimation error covariance. We then present a scheduling algorithm that guarantees that the error covariance will be bounded and that the error will die out exponentially for any detectable LTI system. Simulations are provided to compare the performance of the algorithm against other known techniques.

In this thesis we consider two combinatorial optimization problems that relate to the field of persistent monitoring. In the first part, we extend the classic problem of finding the maximum weight Hamiltonian cycle in a graph to the case where the objective is a submodular function of the edges. We consider a greedy algorithm and a 2-matching based algorithm, and we show that they have approximation factors of 1/2+κ and max{2/(3(2+κ)),(2/3)(1-κ)} respectively, where κ is the curvature of the submodular function. Both algorithms require a number of calls to the submodular function that is cubic to the number of vertices in the graph. We then present a method to solve a multi-objective optimization consisting of both additive edge costs and submodular edge rewards. We provide simulation results to empirically evaluate the performance of the algorithms. Finally, we demonstrate an application in monitoring an environment using an autonomous mobile sensor, where the sensing reward is related to the entropy reduction of a given a set of measurements. In the second part, we study the problem of selecting sensors to obtain the most accurate state estimate of a linear system. The estimator is taken to be a Kalman filter and we attempt to optimize the a posteriori error covariance. For a finite time horizon, we show that, under certain restrictive conditions, the problem can be phrased as a submodular function optimization and that a greedy approach yields a 1-1/(e^(1-1/e))-approximation. Next, for an infinite time horizon, we characterize the exact conditions for the existence of a schedule with bounded estimation error covariance. We then present a scheduling algorithm that guarantees that the error covariance will be bounded and that the error will die out exponentially for any detectable LTI system. Simulations are provided to compare the performance of the algorithm against other known techniques.

Standard local search algorithms for combinatorial optimization problems repeatedly apply small changes to a current solution to improve the problem's given objective function. In contrast, non-oblivious local search algorithms are guided by an auxiliary potential function, which is distinct from the problem's objective. In this thesis, we compare the standard and non-oblivious approaches for a variety of problems, and derive new, improved non-oblivious local search algorithms for several problems in the area of constrained linear and monotone submodular maximization. First, we give a new, randomized approximation algorithm for maximizing a monotone submodular function subject to a matroid constraint. Our algorithm's approximation ratio matches both the known hardness of approximation bounds for the problem and the performance of the recent ``continuous greedy'' algorithm. Unlike the continuous greedy algorithm, our algorithm is straightforward and combinatorial. In the case that the monotone submodular function is a coverage function, we can obtain a further simplified, deterministic algorithm with improved running time. Moving beyond the case of single matroid constraints, we then consider general classes of set systems that capture problems that can be approximated well. While previous such classes have focused primarily on greedy algorithms, we give a new class that captures problems amenable to optimization by local search algorithms. We show that several combinatorial optimization problems can be placed in this class, and give a non-oblivious local search algorithm that delivers improved approximations for a variety of specific problems. In contrast, we show that standard local search algorithms give no improvement over known approximation results for these problems, even when allowed to search larger neighborhoods than their non-oblivious counterparts. Finally, we expand on these results by considering standard local search algorithms for constraint satisfaction problems. We develop conditions under which the approximation ratio of standard local search remains limited even for super-polynomial or exponential local neighborhoods. In the special case of MaxCut, we further show that a variety of techniques including random or greedy initialization, large neighborhoods, and best-improvement pivot rules cannot improve the approximation performance of standard local search.

Thesis (Ph. D.)--University of Washington, 2007. / Includes bibliographical references (p. 134-142).

Cette thèse aborde le problème de l’apprentissage avec des fonctions de perte nonmodulaires. Pour les problèmes de prédiction, où plusieurs sorties sont prédites simultanément, l’affichage du résultat comme un ensemble commun de prédiction est essentiel afin de mieux incorporer les circonstances du monde réel. Dans la minimisation du risque empirique, nous visons à réduire au minimum une somme empirique sur les pertes encourues sur l’échantillon fini avec une certaine perte fonction qui pénalise sur la prévision compte tenu de la réalité du terrain. Dans cette thèse, nous proposons des méthodes analytiques et algorithmiquement efficaces pour traiter les fonctions de perte non-modulaires. L’exactitude et l’évolutivité sont validées par des résultats empiriques. D’abord, nous avons introduit une méthode pour les fonctions de perte supermodulaires, qui est basé sur la méthode d’orientation alternée des multiplicateurs, qui ne dépend que de deux problémes individuels pour la fonction de perte et pour l’infèrence. Deuxièmement, nous proposons une nouvelle fonction de substitution pour les fonctions de perte submodulaires, la Lovász hinge, qui conduit à une compléxité en O(p log p) avec O(p) oracle pour la fonction de perte pour calculer un gradient ou méthode de coupe. Enfin, nous introduisons un opérateur de fonction de substitution convexe pour des fonctions de perte nonmodulaire, qui fournit pour la première fois une solution facile pour les pertes qui ne sont ni supermodular ni submodular. Cet opérateur est basé sur une décomposition canonique submodulairesupermodulaire. / This thesis addresses the problem of learning with non-modular losses. In a prediction problem where multiple outputs are predicted simultaneously, viewing the outcome as a joint set prediction is essential so as to better incorporate real-world circumstances. In empirical risk minimization, we aim at minimizing an empirical sum over losses incurred on the finite sample with some loss function that penalizes on the prediction given the ground truth. In this thesis, we propose tractable and efficient methods for dealing with non-modular loss functions with correctness and scalability validated by empirical results. First, we present the hardness of incorporating supermodular loss functions into the inference term when they have different graphical structures. We then introduce an alternating direction method of multipliers (ADMM) based decomposition method for loss augmented inference, that only depends on two individual solvers for the loss function term and for the inference term as two independent subproblems. Second, we propose a novel surrogate loss function for submodular losses, the Lovász hinge, which leads to O(p log p) complexity with O(p) oracle accesses to the loss function to compute a subgradient or cutting-plane. Finally, we introduce a novel convex surrogate operator for general non-modular loss functions, which provides for the first time a tractable solution for loss functions that are neither supermodular nor submodular. This surrogate is based on a canonical submodular-supermodular decomposition.

Funções submodulares aparecem naturalmente em diversas áreas, tais como probabilidade, geometria e otimização combinatória. Pode-se dizer que o papel desempenhado por essas funções em otimização discreta é similar ao desempenhado por convexidade em otimização contínua. Com efeito, muitos problemas em otimização combinatória podem ser formulados como um problema de minimizar uma função submodular sobre um conjunto apropriado. Além disso, submodularidade está presente em vários teoremas ou problemas combinatórios e freqüentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Nesta dissertação, estudamos aspectos estruturais e algorítmicos de funções submodulares, com ênfase nos recentes avanços em algoritmos combinatórios para minimização dessas funções. Descrevemos com detalhes os primeiros algoritmos combinatórios e fortemente polinomiais para esse propósito, devidos a Schrijver e Iwata, Fleischer e Fujishige, além de algumas outras extensões. Aplicações de submodularidade em otimização combinatória também estão presentes neste trabalho. / Submodular functions arise naturally in various fields, including probability, geometry and combinatorial optimization. The role assumed by these functions in discrete optimization is similar to that played by convexity in continuous optimization. Indeed, we can state many problems in combinatorial optimization as a problem of minimizing a submodular function over an appropriate set. Moreover, submodularity appears in many combinatorial theorems or problems and frequently plays an essencial role in a proof or an algorithm. In this dissertation, we study structural and algorithmic aspects of submodular functions. In particular, we focus on the recent advances in combinatorial algorithms for submodular function minimization. We describe in detail the first combinatorial strongly polynomial-time algorithms for this purpose, due to Schrijver and Iwata, Fleischer, and Fujishige, as well as some extensions. Some applications of submodularity in combinatorial optimization are also included in this work.