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"”.

  1. 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 …

    tamu Repository record for Using Neural Networks to Maximize a Submodular Function (opens in a new tab)

  2. 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 …

    waterloo Repository record for Combinatorial Algorithms for Submodular Function Minimization and Related Problems (opens in a new tab)

  3. 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 …

    lethbridge Repository record for Toward abstractive multi-document summarization using submodular function-based framework, sentence compression and merging (opens in a new tab)

  4. 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 …

    waterloo Repository record for Informative Path Planning and Sensor Scheduling for Persistent Monitoring Tasks (opens in a new tab)

  5. 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 …

    waterloo Repository record for Testing Submodularity (opens in a new tab)

  6. 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 …

    iastate Repository record for Submodular optimization with constraints and fairness: Algorithmic advances and applications (opens in a new tab)

  7. 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 …

    washington Repository record for An Algorithmic Framework for High Dimensional Regression with Dependent Variables (opens in a new tab)

  8. 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 …

    ubc Repository record for Beyond submodular maximization : one-sided smoothness and meta-submodularity (opens in a new tab) Download PDF for Beyond submodular maximization : one-sided smoothness and meta-submodularity (opens in a new tab)

  9. 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 …

    washington Repository record for Submodularity in Natural Language Processing: Algorithms and Applications (opens in a new tab)

  10. 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 …

    gatech Repository record for Resource allocation and subset selection: new approaches at the interface between discrete and continuous optimization (opens in a new tab)

  11. 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 …

    tamu Repository record for Submodular Cover and Maximization: Approximation Algorithms, Bandit Feedback, and Reinforcement Learning (opens in a new tab)

  12. 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 …

    toronto-retro Repository record for Oblivious and Non-oblivious Local Search for Combinatorial Optimization (opens in a new tab)

  13. 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 …

    unsw Repository record for Submodular Optimization in Location-Based Social Networks (opens in a new tab)

  14. 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 …

    gatech Repository record for Optimization and separation for structured submodular functions with constraints (opens in a new tab)

  15. 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. …

    nps Repository record for ROBUST TIME-VARYING FORMATION CONTROL WITH ADAPTIVE SUBMODULARITY (opens in a new tab)

Page 1 of 3