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 72 for “"Submodularity"”.

  1. Testing Submodularity

    We show that for any constants $\epsilon > 0$ 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 …

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

  2. ROBUST TIME-VARYING FORMATION CONTROL WITH ADAPTIVE SUBMODULARITY

    … recompute the optimal formation in simulation. Submodularity is a property of set functions, which guarantees near-optimal performance if a greedy algorithm is used to iteratively select node locations. This effectually reduces the NP-hard combinatorial optimization problem to a polynomial time …

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

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

  4. Submodularity in Dynamics and Control of Networked Systems

    Controlling a networked dynamical system to reach a desired state is a fundamental challenge in applications including transportation, energy, social, and biological systems. One scalable approach to controlling such systems is to directly control the states of a subset of leader nodes, while …

    washington Repository record for Submodularity in Dynamics and Control of Networked Systems (opens in a new tab)

  5. Beyond submodular maximization : one-sided smoothness and meta-submodularity

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

    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)

  6. Bandit learning with non-linear rewards: Submodularity and beyond

    This dissertation focuses on the Combinatorial Multi-Armed Bandit (CMAB) problem, especially in the context where the reward function has non-linear characteristics and the feedback is bandit feedback. The main contributions include proposing the Explore-Then-Commit Greedy (ETCG) algorithm to solve …

    iastate Repository record for Bandit learning with non-linear rewards: Submodularity and beyond (opens in a new tab)

  7. Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity

    Search is an essential technology for various robotic applications and it is also central to human daily activities. Searching for targets efficiently consists of NP-hard problems, but young children can search for targets very efficiently . How humans search for targets efficiently is still a …

    umn Repository record for Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity (opens in a new tab)

  8. Submodular Optimization for Power System Control and Stability

    … problems which are NP-hard to solve. Submodularity is a diminishing-return property of set functions which is analogous to the convexity of continuous functions. A combinatorial optimization problem that possesses submodularity can often be solved by greedy algorithms effectively with …

    washington Repository record for Submodular Optimization for Power System Control and Stability (opens in a new tab)

  9. OBSERVATIONAL OVERSIGHT FOR UNDERSTANDING TRUST IN INTERACTIVE HUMAN AND AI SYSTEMS

    … of a ground team element, the NCS uses adaptive submodularity to configure a topology of network nodes that maximizes communications, sensor coverage, and network robustness. Interaction with the NCS is accomplished with a virtual reality (VR) interface by suggesting UxV positions to be evaluated …

    nps Repository record for OBSERVATIONAL OVERSIGHT FOR UNDERSTANDING TRUST IN INTERACTIVE HUMAN AND AI SYSTEMS (opens in a new tab)

  10. SUBMODULAR OPTIMIZATION AND ITS APPLICATIONS

    … concept of supermodularity whose "'twin" concept submodularity was first studied in relation to matriods. Interestingly recent progress has shown that many aspects of submodularity seem to mirror many important properties of convexity in "continuous" optimization. In this sense, we may regard …

    nus Repository record for SUBMODULAR OPTIMIZATION AND ITS APPLICATIONS (opens in a new tab) Download file for SUBMODULAR OPTIMIZATION AND ITS APPLICATIONS (opens in a new tab)

  11. Submodular Optimization and Data Processing

    … this dissertation, we investigate how to apply submodularity to these two data processing paradigms. In the first part of this thesis, we study the connection of submodularity to the data summarization paradigm. First we show that data summarization subsumes a number of applications, including …

    washington Repository record for Submodular Optimization and Data Processing (opens in a new tab)

  12. DISTRIBUTED SUBMODULAR OPTIMIZATION FOR A UXV NETWORKED CONTROL SYSTEM

    … prohibitive. In this thesis, we explore using submodularity to solve this problem. This approach gives near-optimality guarantees while reducing the complexity of the problem, allowing solutions to be found in near real-time. A simple, novel distributed submodular approach to NCS control was …

    nps Repository record for DISTRIBUTED SUBMODULAR OPTIMIZATION FOR A UXV NETWORKED CONTROL SYSTEM (opens in a new tab)

  13. Efficient and robust resource allocation for network function virtualization

    … theory and utilize the property of sequence submodularity along with the primal-dual technique to design two approximation algorithms. Finally, we perform extensive trace-driven simulations to show the effectiveness of the proposed algorithms. While the NFV paradigm offers great flexibility …

    temple Repository record for Efficient and robust resource allocation for network function virtualization (opens in a new tab)

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

  15. Optimization and separation for structured submodular functions with constraints

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

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

  16. Scalable, information-based sensor tasking for space situational awareness

    … suboptimally using a submodular surrogate. Submodularity is exploited to admit a tractable, performance-bounded solution. A distributed, game-theoretic algorithm is applied to solve this problem, providing scalability and robustness. The proposed algorithm is validated using simulated data …

    texas Repository record for Scalable, information-based sensor tasking for space situational awareness (opens in a new tab)

  17. Integer Programming Approaches to Cancer Treatment: Objective Selection in Intensity-Modulated Radiation Therapy and Chemotherapy Treatment Design

    … to the greedy algorithm, we study approximate submodularity in other areas in discrete optimization. The second cancer treatment problem is combination chemotherapy optimization, which requires merging differential equations that model dynamics together with discrete decision variables for …

    rice Repository record for Integer Programming Approaches to Cancer Treatment: Objective Selection in Intensity-Modulated Radiation Therapy and Chemotherapy Treatment Design (opens in a new tab)

Page 1 of 4