Search

Submodular functions are fundamental to combinatorial optimization. Many interesting problems can be formulated as special cases of problems involving submodular functions. In this work, we consider the problem of approximating symmetric submodular functions everywhere using hypergraph cut functions. Devanur, Dughmi, Schwartz, Sharma, and Singh [Devanur et al., 2013] showed that symmetric submodular functions over n-element ground sets cannot be approximated within (n/8)-factor using a graph cut function and raised the question of approximating them using hypergraph cut functions. Our main result is that there exist symmetric submodular functions over n-element ground sets that cannot be approximated within a o(n^{1/3}/log² n)-factor using a hypergraph cut function. On the positive side, we show that symmetrized concave linear functions and symmetrized rank functions of uniform matroids and partition matroids can be constant-approximated using hypergraph cut functions.

Social media has created new ways for citizens to stay informed on societal matters and participate in political discourse. However, with its algorithmically-curated and virally-propagating content, social media has contributed further to the polarization of opinions by reinforcing users’ existing viewpoints. An emerging line of research seeks to understand how content-recommendation algorithms can be re-designed to mitigate societal polarization amplified by social-media interactions. In this paper, we study the problem of allocating seed users to opposing campaigns: by drawing on the equal-time rule of political campaigning on traditional media, our goal is to allocate seed users to campaigners with the aim to maximize the expected number of users who are co-exposed to both campaigns. We show that the problem of maximizing co-exposure is NP-hard and its objective function is neither submodular nor supermodular. However, by exploiting a connection to a submodular function that acts as a lower bound to the objective, we are able to devise a greedy algorithm with provable approximation guarantee. We further provide a scalable instantiation of our approximation algorithm by introducing a novel extension to the notion of random reverse-reachable sets for efficiently estimating the expected co-exposure. We experimentally demonstrate the quality of our proposal on real-world social networks., QC 20210906

type:Note, In this paper, we prove that there exists a combinatorial 3-approximation algorithm for the submodular vertex cover problem with submodular penalties introduced by Xu, Wang, Du, and Wu.

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2^[n] → ℝ, find an element of arg min_S {f(S)} using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. We provide a query lower bound of 2n for submodular function minimization, a 3n/2-2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a binom{n}{2} query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our 3n/2-2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2-2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n+1 for s-t mincut, even in a directed, weighted graph.

Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge e exists, we need to perform an expensive test, in which case the edge e appears independently with a known probability p_e. Given a budget on the total cost of the tests, our goal is to find a testing strategy that maximizes the expected maximum matching size. The above application is an example of the stochastic probing problem. In general the optimal stochastic probing strategy is difficult to find because it is adaptive - decides on the next edge to probe based on the outcomes of the probed edges. An alternate approach is to show the adaptivity gap is small, i.e., the best non-adaptive strategy always has a value close to the best adaptive strategy. This allows us to focus on designing non-adaptive strategies that are much simpler. Previous works, however, have focused on Bernoulli random variables that can only capture whether an edge appears or not. In this work we introduce a multi-value stochastic probing problem, which can also model situations where the weight of an edge has a probability distribution over multiple values. Our main technical contribution is to obtain (near) optimal bounds for the (worst-case) adaptivity gaps for multi-value stochastic probing over prefix-closed constraints. For a monotone submodular function, we show the adaptivity gap is at most 2 and provide a matching lower bound. For a weighted rank function of a k-extendible system (a generalization of intersection of k matroids), we show the adaptivity gap is between O(k log k) and k. None of these results were known even in the Bernoulli case where both our upper and lower bounds also apply, thereby resolving an open question of Gupta et al. [Gupta et al., 2017].

In this thesis we study fundamental problems that arise in optimization and its applications. We present provably efficient algorithms that achieve better running times or approximation guarantees than previously known. Our method draws on the toolkit from convex and combinatorial optimization as well as economics. By intertwining techniques from these disciplines, we are able to make progress on multiple old and new problems, some of which have stood open for many years. Main results of this thesis include the following:Convex Programming: We show how to solve convex programming with an expected O(n log(nR/\epsilon)) evaluations of the separation oracle and additional time O(n^3\log^{O(1)}(nR/\epsilon)). This matches the oracle complexity and improves upon the O(n^{\omega+1}\log(nR/\epsilon)) additional time of the previous fastest algorithm achieved over 25 years ago for the current value of the matrix multiplication constant when R/\epsilon=O(\poly(n)).Submodular Function Minimization: We provide new weakly and strongly polynomial time algorithms with a running time of O(n^{2}\log nM\cdot\text{EO}+n^{3}\log^{O(1)}nM) and O(n^{3}\log^{2}n\cdot\text{EO}+n^{4}\log^{O(1)}n), improving upon the previous best of O((n^{4}\cdot\text{EO}+n^{5})\log M) and O(n^{5}\cdot\text{EO}+n^{6}) respectively. We also provide the first subquadratic time algorithm for computing an approximately optimal solution.Matroid Intersection: We provide new algorithms with a running time of O(nr\mathcal{T_{\text{rank}}}\log n\log(nM)+n^{3}\log^{O(1)}nM) and O(n^{2}\mathcal{T_{\text{ind}}}\log(nM)+n^{3}\log^{O(1)}nM , achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle.Submodular Flow: We obtain a faster weakly polynomial running time of O(n^{2}\log(nCU)\cdot\EO+n^{3}\log^{O(1)}(nCU)), improving upon the previous best of O(mn^{5}\log(nU)\cdot\EO) and O\left(n^{4}

In this thesis we study fundamental problems that arise in optimization and its applications. We present provably efficient algorithms that achieve better running times or approximation guarantees than previously known. Our method draws on the toolkit from convex and combinatorial optimization as well as economics. By intertwining techniques from these disciplines, we are able to make progress on multiple old and new problems, some of which have stood open for many years. Main results of this thesis include the following:Convex Programming: We show how to solve convex programming with an expected O(n log(nR/\epsilon)) evaluations of the separation oracle and additional time O(n^3\log^{O(1)}(nR/\epsilon)). This matches the oracle complexity and improves upon the O(n^{\omega+1}\log(nR/\epsilon)) additional time of the previous fastest algorithm achieved over 25 years ago for the current value of the matrix multiplication constant when R/\epsilon=O(\poly(n)).Submodular Function Minimization: We provide new weakly and strongly polynomial time algorithms with a running time of O(n^{2}\log nM\cdot\text{EO}+n^{3}\log^{O(1)}nM) and O(n^{3}\log^{2}n\cdot\text{EO}+n^{4}\log^{O(1)}n), improving upon the previous best of O((n^{4}\cdot\text{EO}+n^{5})\log M) and O(n^{5}\cdot\text{EO}+n^{6}) respectively. We also provide the first subquadratic time algorithm for computing an approximately optimal solution.Matroid Intersection: We provide new algorithms with a running time of O(nr\mathcal{T_{\text{rank}}}\log n\log(nM)+n^{3}\log^{O(1)}nM) and O(n^{2}\mathcal{T_{\text{ind}}}\log(nM)+n^{3}\log^{O(1)}nM , achieving the first quadratic bound on the query complexity for the independence and rank oracles. In the unweighted case, this is the first improvement since 1986 for independence oracle.Submodular Flow: We obtain a faster weakly polynomial running time of O(n^{2}\log(nCU)\cdot\EO+n^{3}\log^{O(1)}(nCU)), improving upon the previous best of O(mn^{5}\log(nU)\cdot\EO) and O\left(n^{4}

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs depending on a fixed set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified in this sense. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. We remark that in this paper the infinite domain will always be the set of rational numbers. We show that such VCSPs can be solved in polynomial time when the cost functions are additionally submodular, and that this is indeed a maximally tractable class: adding any cost function that is not submodular leads to an NP-hard VCSP.

Capacitated fixed-charge network flow problems (CFCNF) are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. We model CFCNF as a linear mixed-integer program and study the polyhedral structure of various path networks.We investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a fast computation of parametric minimum cuts on a path, and they generalize the well-known flow cover and flow pack inequalities for the single-node relaxations of fixed-charge flow models. Computational results demonstrate the effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.Moreover, we consider single item lot-sizing problems with backlogging and inventory bounds and fixed costs (LSBIB). Using the underlying fixed-charge network structure of LSBIB, we derive explicit path pack inequalities that are proposed in this thesis. These inequalities are generalizations of the valid inequalities proposed by Atamturk and Kucukyavuz (2005) for lot-sizing problems under the existence of backlogging. Furthermore, we propose extensions of these inequalities where the binary variables for inventory and backlogging are lifted. Finally, we present computational results suggest that show the effectiveness of both path pack and extended path pack inequalities when used in a branch-and-cut algorithm.

Huber et al. (SIAM J Comput 43:1064–1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28:1828–1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1–9, 2014) also showed a min–max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.

Huber et al. (SIAM J Comput 43:1064–1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28:1828–1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1–9, 2014) also showed a min–max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.

Capacitated fixed-charge network flow problems (CFCNF) are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. We model CFCNF as a linear mixed-integer program and study the polyhedral structure of various path networks.We investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a fast computation of parametric minimum cuts on a path, and they generalize the well-known flow cover and flow pack inequalities for the single-node relaxations of fixed-charge flow models. Computational results demonstrate the effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.Moreover, we consider single item lot-sizing problems with backlogging and inventory bounds and fixed costs (LSBIB). Using the underlying fixed-charge network structure of LSBIB, we derive explicit path pack inequalities that are proposed in this thesis. These inequalities are generalizations of the valid inequalities proposed by Atamturk and Kucukyavuz (2005) for lot-sizing problems under the existence of backlogging. Furthermore, we propose extensions of these inequalities where the binary variables for inventory and backlogging are lifted. Finally, we present computational results suggest that show the effectiveness of both path pack and extended path pack inequalities when used in a branch-and-cut algorithm.

Huber et al. (SIAM J Comput 43:1064–1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28:1828–1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12:1–9, 2014) also showed a min–max theorem that characterizes the skew-bisubmodular function minimization, but devising a combinatorial polynomial algorithm for skew-bisubmodular function minimization was left open. In the present paper we give first combinatorial (weakly and strongly) polynomial algorithms for skew-bisubmodular function minimization.

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.363-epsilon)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4-epsilon)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and epsilon.

Binary Conic Quadratic Knapsack set is the lower level set of the conic quadratic set functions. They are natural generalizations of linear knapsack sets, and have several applications in several areas, such as, combinatorial optimization, finance, and optimal control. In particular, conic quadratic knapsacks can be used to model the 0-1 linear knapsack sets with uncertain coefficients. In addition to being of theoretical interest, these problems are practically relevant as they can be used to mathematically formulate probabilistic and robust equivalents of the deterministic combinatorial and decision problems.Although the non-linear binary sets, specifically the quadratic knapsack sets have been studied in the literature, the specific combinatorial structure associated with these sets remains to be explored. Non-linear binary sets involving bilinear terms are at present solved using a combination of lift and project relaxations and a branch-and-bound scheme that solves continuous non-linear relaxations at the nodes of a branch-and-bound search tree. The branch-and-cut methods developed for general integer conic quadratic sets make use of the problem's geometrical structure for removing fractional solutions of conic relaxations can be employed to solve the particular case of 0-1 conic quadratic knapsacks, however these approaches do not utilize the additional combinatorial structure specific to these sets. Motivated by the performance improvement observed by exploring geometrical structure for conic mixed integer programs, and the fact that exploring combinatorial structure has proven extremely useful in addressing the linear $0-1$ knapsack sets, we expect this to work well in the case of conic quadratic knapsacks as well.In this dissertation, we study pure-binary programs with conic quadratic constraints and develop branch-and-cut algorithms to solve them with applications to robust network design problem. First, we study the combinatorial structure embedded into t

Binary Conic Quadratic Knapsack set is the lower level set of the conic quadratic set functions. They are natural generalizations of linear knapsack sets, and have several applications in several areas, such as, combinatorial optimization, finance, and optimal control. In particular, conic quadratic knapsacks can be used to model the 0-1 linear knapsack sets with uncertain coefficients. In addition to being of theoretical interest, these problems are practically relevant as they can be used to mathematically formulate probabilistic and robust equivalents of the deterministic combinatorial and decision problems.Although the non-linear binary sets, specifically the quadratic knapsack sets have been studied in the literature, the specific combinatorial structure associated with these sets remains to be explored. Non-linear binary sets involving bilinear terms are at present solved using a combination of lift and project relaxations and a branch-and-bound scheme that solves continuous non-linear relaxations at the nodes of a branch-and-bound search tree. The branch-and-cut methods developed for general integer conic quadratic sets make use of the problem's geometrical structure for removing fractional solutions of conic relaxations can be employed to solve the particular case of 0-1 conic quadratic knapsacks, however these approaches do not utilize the additional combinatorial structure specific to these sets. Motivated by the performance improvement observed by exploring geometrical structure for conic mixed integer programs, and the fact that exploring combinatorial structure has proven extremely useful in addressing the linear $0-1$ knapsack sets, we expect this to work well in the case of conic quadratic knapsacks as well.In this dissertation, we study pure-binary programs with conic quadratic constraints and develop branch-and-cut algorithms to solve them with applications to robust network design problem. First, we study the combinatorial structure embedded into t

In this paper we study the connections among finite topological spaces, FD-relations (or databases) and submodular functions. We interpret the properties of closure operators of finite topological spaces, in terms of FD-relations and submodular functions, we also characterize concepts and properties such that: accumulation points, exterior point, closed set, dense set and separation axioms., En este artículo se estudian las conexiones entre los espacios topológicos finitos, las FD-relaciones (o bases de datos) y las funciones submodulares. Se interpretan las propiedades de los operadores de clausura de un espacio topológico finito en términos de FD-relaciones y funciones submodulares, como también algunos conceptos y propiedades tales como: puntos de acumulación, punto exterior, conjunto cerrado, conjunto denso y los axiomas de separación.

In this paper we study the connections among finite topological spaces, FD-relations (or databases) and submodular functions. We interpret the properties of closure operators of finite topological spaces, in terms of FD-relations and submodular functions, we also characterize concepts and properties such that: accumulation points, exterior point, closed set, dense set and separation axioms., En este artículo se estudian las conexiones entre los espacios topológicos finitos, las FD-relaciones (o bases de datos) y las funciones submodulares. Se interpretan las propiedades de los operadores de clausura de un espacio topológico finito en términos de FD-relaciones y funciones submodulares, como también algunos conceptos y propiedades tales como: puntos de acumulación, punto exterior, conjunto cerrado, conjunto denso y los axiomas de separación.

This is a supplementary note on M. X. Goemans, S. Iwata, and R. Zenklusen’s paper that proposes a flow model based on polylinking systems. Their flow model is a series (or tandem) connection of polylinking systems. We can consider an apparently more general model of a polylinking flow network which consists of an ordinary arc-capacitated network endowed with polylinking systems on the vertex set, one for each vertex of the network. This is a natural, apparent generalization of polymatroidal flow model of E. L. Lawler and C. U. Martel and of generalized-polymatroidal flow model of R. Hassin. We give a max-flow min-cut formula for the polylinking network flow problem and discuss some acyclic flow property of polylinking flows.

This report describes the outcome of the project A Submodularity Framework for Data Subset Selection. The goal of the project was to develop and evaluate novel submodular functions for the purpose of subselecting large sets of acoustic and text data. The subselected data sets were used to train acoustic models for automatic speech recognition or translation models for machine translation, respectively. The submodular selection techniques were evaluated against random data selection and the best comparable data selection technique previously reported in the literature. Our results demonstrate that submodular data selection outperforms all baseline techniques, i.e. for a fixed data subset size, submodular selection resulted in systems with better performance. Additionally, submodular selection was applied to the problem of feature selection, where it outperformed standard modular feature selection techniques.

A loss of heterozygosity (LOH) event occurs when, by the laws of Mendelian inheritance, an individual should be heterozygote at a given site but, due to a deletion polymorphism, is not. Deletions play an important role in human disease and their detection could provide fundamental insights for the development of new diagnostics and treatments. In this paper, we investigate the parsimonious loss of heterozygosity problem (PLOHP), i.e. the problem of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas. Specifically, we generalize Halldórsson et al.'s work by providing a more general formulation of the PLOHP and by showing how one can incorporate different recombination rates and prior knowledge about the locations of deletions. Moreover, we show that the PLOHP can be formulated as a specific version of the clique partition problem in a particular class of graphs called undirected catch-point interval graphs and we prove its general NP-hardness. Finally, we provide a state-of-the-art integer programming (IP) formulation and strengthening valid inequalities to exactly solve real instances of the PLOHP containing up to 9,000 individuals and 3,000 SNPs. Our results give perspectives on the mathematics of the PLOHP and suggest new directions on the development of future efficient exact solution approaches. © 2013 IEEE., SCOPUS: ar.j, info:eu-repo/semantics/published

A loss of heterozygosity (LOH) event occurs when, by the laws of Mendelian inheritance, an individual should be heterozygote at a given site but, due to a deletion polymorphism, is not. Deletions play an important role in human disease and their detection could provide fundamental insights for the development of new diagnostics and treatments. In this paper, we investigate the parsimonious loss of heterozygosity problem (PLOHP), i.e. the problem of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas. Specifically, we generalize Halldórsson et al.'s work by providing a more general formulation of the PLOHP and by showing how one can incorporate different recombination rates and prior knowledge about the locations of deletions. Moreover, we show that the PLOHP can be formulated as a specific version of the clique partition problem in a particular class of graphs called undirected catch-point interval graphs and we prove its general NP-hardness. Finally, we provide a state-of-the-art integer programming (IP) formulation and strengthening valid inequalities to exactly solve real instances of the PLOHP containing up to 9,000 individuals and 3,000 SNPs. Our results give perspectives on the mathematics of the PLOHP and suggest new directions on the development of future efficient exact solution approaches. © 2013 IEEE., SCOPUS: ar.j, info:eu-repo/semantics/published

We investigate the Parsimonious Loss of Heterozygosity Problem (PLOHP), i.e. the problem of partitioning suspected polymorphisms of a set of individuals into the minimum number of deletion areas. We generalize the work of Halldórsson et al.' by showing how one can incorporate prior knowledge about the location of deletion; we prove the general -hardness of the problem and we provide a state-of-the-art mixed integer programming formulation and a number of possible strengthening valid inequalities able to exactly solve practical instances of the PLHOP containing up to 9.000 individuals and 3000 SNPs within 12 hours compute time. © 2012 Springer-Verlag., SCOPUS: cp.k, info:eu-repo/semantics/published

We investigate the Parsimonious Loss of Heterozygosity Problem (PLOHP), i.e. the problem of partitioning suspected polymorphisms of a set of individuals into the minimum number of deletion areas. We generalize the work of Halldórsson et al.' by showing how one can incorporate prior knowledge about the location of deletion; we prove the general -hardness of the problem and we provide a state-of-the-art mixed integer programming formulation and a number of possible strengthening valid inequalities able to exactly solve practical instances of the PLHOP containing up to 9.000 individuals and 3000 SNPs within 12 hours compute time. © 2012 Springer-Verlag., SCOPUS: cp.k, info:eu-repo/semantics/published

In this paper we consider the problem of finding the densest subset subject to co-matroid constraints. We are given a monotone supermodular set function f defined over a universe U, and the density of a subset S is defined to be f(S)/|S|. This generalizes the concept of graph density. Co-matroid constraints are the following: given matroid M a set S is feasible, iff the complement of S is independent in the matroid. Under such constraints, the problem becomes NP-hard. The specific case of graph density has been considered in literature under specific co-matroid constraints, for example, the cardinality matroid and the partition matroid. We show a 2-approximation for finding the densest subset subject to co-matroid constraints. Thereby we improve the approximation guarantees for the result for partition matroids in the literature.

In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409–422, 2006) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26–33, 2003). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al. (SIAM Journal on Control and Optimization 31(2):387–438, 1993) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253–271, 1995), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term.

In a recent paper Boykov et al. (LNCS, Vol. 3953, pp. 409–422, 2006) propose an approach for computing curve and surface evolution using a variational approach and the geo-cuts method of Boykov and Kolmogorov (International conference on computer vision, pp. 26–33, 2003). We recall in this paper how this is related to well-known approaches for mean curvature motion, introduced by Almgren et al. (SIAM Journal on Control and Optimization 31(2):387–438, 1993) and Luckhaus and Sturzenhecker (Calculus of Variations and Partial Differential Equations 3(2):253–271, 1995), and show how the corresponding problems can be solved with sub-pixel accuracy using Parametric Maximum Flow techniques. This provides interesting algorithms for computing crystalline curvature motion, possibly with a forcing term.

This thesis develops online algorithms that can be used to solve a wide variety of NP-hard problems more efficiently in practice. The common approach taken by all our online algorithms is to improve the performance of one or more existing algorithms for a specific NP-hard problem by adapting the algorithms to the sequence of problem instance(s) they are run on. We begin by presenting an algorithm for solving a specific class of online resource allocation problems. Our online algorithm can be applied in environments where abstract jobs arrive one at a time, and one can complete the jobs by investing time in a number of abstract activities. Provided the jobs and activities satisfy certain technical conditions, our online algorithm is guaranteed to perform almost as well as any fixed schedule for investing time in the various activities, according to two natural measures of performance: 1. the average time required to complete each job, and 2. the number of jobs completed within time T, for some fixed deadline T>0. In particular, our online algorithm's guarantees apply if the job can be written as a monotone, submodular function of a set of pairs of the form (upsilon, tau), where tau is the time invested in activity upsilon. Under the 1st objective, the offline version of this problem generalizes MIN-SUM SET COVER and the related PIPELINED SET COVER problem. Under the 2nd objective, the offline version of this problem generalizes the problem of maximizing a monotone, submodular set function subject to a knapsack constraint. Our online algorithm has potential applications in a number of areas, including the design of algorithm portfolios, database query processing, and sensor placement. We apply this online algorithm to the following problem. We are given k algorithms, and are fed, one at a time, a sequence of problem instances to solve. We may solve each instance using any of the algorithms, we may interleave the execution of the algorithms, and we may restart them., Sponsored in part by the National Science Foundation.

We consider the following two problems. We are given as input a set of activities and a set of jobs to complete. Our goal is to devise a schedule for allocating time to the various activities so as to achieve one of two objectives: minimizing the average time required to complete each job, or maximizing the number of jobs completed within a fixed time. Formally, a schedule is a sequence where each pair represents investing time in an activity. We assume that the fraction of jobs completed is a monotone submodular function of the sequence of pairs that appear in a schedule. We consider these problems in the online setting, in which the jobs arrive one at a time and we must finish each job "via some schedule" before moving on to the next. We give an efficient online algorithm for this problem whose worst-case asymptotic performance is simultaneously optimal for both objectives in the sense that its performance ratio "with respect to the optimal static schedule" converges to the best approximation ratios for the corresponding offline problems. Finally, we evaluate this algorithm experimentally by using it to learn, online, a schedule for allocating CPU time to the solvers entered in the 2007 SAT solver competition., Sponsored in part by Defense Advanced Research Projects Agency (DARPA).