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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 4