Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 57 for “"submodular function"”.
-
Using Neural Networks to Maximize a Submodular Function
… in continuous space, both convex and concave functions can be efficiently and effectively optimized due to its convexity and con- cavity. It seems that optimization in discrete functions is worth exploring. The most appealing point we see in a submodular set function has to be its natural …
-
Combinatorial Algorithms for Submodular Function Minimization and Related Problems
Submodular functions are common in combinatorics; examples include the cut capacity function of a graph and the rank function of a matroid. The submodular function minimization problem generalizes the classical minimum cut problem and also contains a number of other combinatorial optimization …
-
Toward abstractive multi-document summarization using submodular function-based framework, sentence compression and merging
… using different abstraction-based methods and submodularity. Our proposed model considers summarization as a budgeted submodular function maximization problem. The model integrates three important measures of a summary - namely importance, coverage, and non-redundancy, and we design a …
-
Informative Path Planning and Sensor Scheduling for Persistent Monitoring Tasks
… 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 …
-
Testing Submodularity
… and $p \ge 1$, given oracle access to an unknown function $f : \{0,1\}^n \to [0,1]$ it is possible to determine if the function is submodular or is $\epsilon$-far from every submodular function, in $\ell_p$ distance, with a \emph{constant} number of queries to the oracle. We refer to the process …
-
Submodular optimization with constraints and fairness: Algorithmic advances and applications
Submodular function optimization is a fundamental tool for modeling complex interactions in machine learning and graph mining. In this thesis, we investigate constrained submodular maximization problems, their variants, and $k$-submodular maximization problems with size constraints and fairness …
-
An Algorithmic Framework for High Dimensional Regression with Dependent Variables
… models, network flows, and recent results in submodular function theory. This work unifies key aspects of these problems under a common theory, leading to novel methods for working with several important models of interest in statistics, machine learning and computer vision. Most notably, we …
-
Beyond submodular maximization : one-sided smoothness and meta-submodularity
… there are well-developed tools for maximizing a submodular function f(S) subject to a matroid constraint S ∈ ℳ, there is much less work on the corresponding supermodular maximization problems. We develop new techniques for attacking these problems inspired by the continuous greedy method applied …
-
Submodularity in Natural Language Processing: Algorithms and Applications
… problems challenge to solve. On the other hand, submodularity, also known as the discrete analogous of convexity, makes many combinatorial optimization problems either tractable or approximable where otherwise neither would be possible. Whether submodularity is applicable to natural language …
-
Resource allocation and subset selection: new approaches at the interface between discrete and continuous optimization
… bipartite matching problem and the constrained submodular function maximization problem. In the first part of this thesis, we consider novel polyhedral approaches for the i.i.d. online variant of the classical bipartite matching problem defined as follows: one side of the bipartition is fixed …
-
Submodular Cover and Maximization: Approximation Algorithms, Bandit Feedback, and Reinforcement Learning
… diagnosis. Among discrete optimization problems, submodular optimization stands out as particularly important, arising in numerous real-world applications including influence maximization in recommendation systems, data summarization, and neural network pruning. The study of submodular …
-
Oblivious and Non-oblivious Local Search for Combinatorial Optimization
… 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 …
-
Submodular Optimization in Location-Based Social Networks
… As an important research topic in LBSN, submodular optimization in location-based social networks (SO-LBSN) has been considered by many studies, because it is useful in applications such as service location selection, marketing, and tourist trip planning. However, due to the rich …
-
Optimization and separation for structured submodular functions with constraints
… 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 …
-
ROBUST TIME-VARYING FORMATION CONTROL WITH ADAPTIVE SUBMODULARITY
… nodes relative to virtual leaders. A utility function that encapsulates the sensing, communications, robustness, and dynamics of the NCS is designed and shown to be submodular. Submodular function maximization is then used to adaptively recompute the optimal formation in simulation. …
Page 1 of 3