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 44 for “"Supermodular"”.
-
Arithmetic Combinations of Submodular and Supermodular Optimization and Submodular Generalized Matching for Peptide Identification in Tandem Mass Spectrometry
… is usually not a simple submodular function (or supermodular function) but is naturally written as an arithmetic combination of submodular and/or supermodular functions. For the first part of this thesis work, we study the property of the widest arithmetic combinations of submodular and …
-
Ordering risk bounds in partially specified factor models
… conditions on the ✳-product of copulas and supermodular ordering conditions on the upper resp. lower product of bivariate copulas which describe the dependence structure of general specified resp. conditionally comonotonic resp. conditionally countermonotonic random vectors. In the case of …
-
SUBMODULAR OPTIMIZATION AND ITS APPLICATIONS
… was actually equivalent to the 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" …
-
SUPER-MODULAR CATEGORIES
… topological phases of matter. Mathematically, supermodular categories are important alternatives to modular categories as any unitary pre-modular category is the equivariantization of either a modular or a super-modular category. Unlike the modular case, one does not have a representation of …
-
Dependence structures in Lévy-type Markov processes
… dependence, which include association, positive supermodular association (PSA), positive supermodular dependence (PSD), and positive orthant dependence (POD), and more. We will give a history of the characterization of these notions of positive dependence for infinitely divisible distributions, …
-
Beyond submodular maximization : one-sided smoothness and meta-submodularity
… ℳ, 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 to the multi-linear extension of a submodular function. We first adapt the continuous greedy algorithm to …
-
Essays on information and mechanism design
… The first chapter of the dissertation focuses on supermodular mechanism design in environments with arbitrary finite type spaces and interdependent valuations. In these environments, the designer may have to use Bayesian equilibrium as a solution concept, because ex post implementation may not be …
-
M♮-convexity, S-convexity, and their applications in operations
… applicable to optimization models with supermodular objective function maximization, does not apply. In this thesis, by employing a key concept in discrete convex analysis, M♮-convexity, we establish conditions under which the optimal solutions are nonincreasing in the parameters and the …
-
On the orientation of hypergraphs
… hypergraphs that admit out-orientations covering supermodular-type connectivity requirements. For this, we follow a paper of Frank. We also study the Steiner rooted orientation problem. Given a hypergraph and a subset of vertices S ⊆ V, the goal is to give necessary and sufficient conditions for …
-
Network Design with node constraints and Maximum Network Lifetime problems
… are defined by an intersecting or crossing supermodular set function and the degree bounds are defined for the out-degrees of nodes or for the in-degrees or both. Since most of the DWDCN problems are known to be NP-hard, we consider approximation algorithms. While requiring that all …
-
Feedback Loops in Interactive Machine Learning: Online Weakly-Submodular Learning and Probing for Missing Labels
… that are neither purely submodular nor purely supermodular. We extend Gaussian Process contextual bandits to objectives that are BP-decomposable (a sum of monotone submodular and supermodular terms) or weakly submodular. We introduce a novel separate-feedback framework where observations are …
-
Essays on Matching and Auction Theory
… type framework, moving away from the supermodular paradigm that is the workhorse of models of matching with incomplete information.
-
Submodularity in Dynamics and Control of Networked Systems
… We prove that the error due to link noise is a supermodular function of the set of leader nodes, leading to the first polynomial-time algorithms for minimizing error due to link noise with provable optimality bounds. We develop our approach for networks with static topologies, as well as dynamic …
-
Welfare maximization for complementary and competing items and their applications : analysis and algorithm using a utility driven model for achieving better social influence
… the objective function is neither submodular nor supermodular, a constant or instance-dependent approximation can still be achieved. With comprehensive experiments on real and synthetic datasets, we demonstrate that our algorithms significantly outperform all baselines on large real social …
-
Contracts for Density and Packing Functions
… the case when the principal's reward function is supermodular and is based on some graph. Recently, Deo-Campo Vuong et al. showed that for this problem it is impossible to provide any finite multiplicative approximation or additive FPTAS unless P=NP. On a positive note, Deo-Campo Vuong et al. …
-
Optimizing the Structure of Diffusion Networks: Theory and Algorithms
… modification problems under this model have supermodular objective functions. This surprising property facilitates computational advancements on multiple fronts: it allows us to design efficient data structures and scalable algorithms with provable approximation guarantees, despite the …
-
A Spectral Decomposition Heuristic for Near Optimal Capture Sets In Consensus Models
… The objective function of interest F(A) is supermodular and therefore, a greedy technique provides a ( 1 - 1/e) approximation to the optimal solution. While the greedy technique provides a guaranteed approximation it comes at the cost of being O(k n^4). This work develops the Spectral …
-
Diversity and Novelty: Measurement, Learning and Optimization
… matching problems. We propose new submodular and supermodular objective functions to measure diversity and develop multiple matching algorithms for diverse team formation in offline and online cases. Finally, in the third part, we demonstrate filtering and ranking of ideas using diversity metrics …
-
Application of Game Theory Analysis in Epidemiology and Service Management
… infections, the underlying game is supermodular and that a unique Pareto optimal Nash equilibrium exists. Further, we identify sufficient conditions under which the optimal solution of a central planner constitutes a Pareto improvement over the decentralized equilibrium.</p><p>The …
Page 1 of 3