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 17 of 17 for “"Submodular Function"”.
-
Matchings, matroids and submodular functions
… matching, matroid intersection, and submodular function minimization. We develop simple, efficient, randomized algorithms for the first two problems, and prove new lower bounds for the last two problems. For the matching problem, we give an algorithm for constructing perfect or …
-
Machine learning for selecting parallel I/O benchmark applications
… an important problem. We investigate the use of submodular function maximization as a way to select a set of I/O benchmark applications using measures of similarities between applications computed from I/O statistics obtained from the Darshan logs of their jobs. Our optimization problem …
-
Scheduling to minimize power consumption using submodular functions
… for logarithmic approximation to maximizing any submodular function subject to budget constraints. We also introduce the online version of this scheduling problem, and show its relation to the classical secretary problem. In order to obtain constant competitive algorithms for this online version, …
-
Generating secret in a network
… capacity as mutual dependence. New identities in submodular function optimization and matroid theory are discovered in proving these results. A framework is also developed to view matroids as graphs, allowing certain theory on graphs to generalize to matroids. In order to study cooperation schemes …
-
Faster algorithms for convex and combinatorial optimization
… three fundamental problems in computer science: submodular function minimization, matroid intersection, and semidefinite programming. --Graph Sparsification: We obtain the first almost-linear time randomized algorithm for spectrally approximating any graph by one with just a linear number of …
-
Vignettes on robust combinatorial optimization
… maximizing multiple objectives, all monotone submodular, subject to a cardinality constraint. We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose several algorithms (including one with the best achievable …
-
Contributions on secretary problems, independent sets of rectangles and related problems
… of finding nonempty minimizers of a symmetric submodular function over any family of sets closed under inclusion. We give an efficient O(ns)-time algorithm for this task, based on Queyranne's pendant pair technique for minimizing unconstrained symmetric submodular functions. We extend this …
-
Optimization problems in networks and queues
… dynamic resource allocation with concave cost functions that capture user dissatisfaction from resource shortfalls. We analyze two non-convex optimization problems in this domain and present polynomial-time algorithms with provable guarantees on reaching their respective global optima. This …
-
Submodular Optimization in Multi-Robot Teams: Robustness, Resilience, and Decentralization
… optimization domain with the help of submodular and matroid optimization techniques. As a motivating example, we use a multi-robot environmental monitoring problem to extract the general formulation of a multi-robot decision-making problem. Consider the problem of deploying multi-agent …
-
Distributionally Ambiguous Stackelberg Combinatorial Games for Submodular Optimization and Camera View-Frame Placement
… when the defender's objective is maximizing k-submodular func- tion, under both DRO and DRR frameworks. To solve problem, we derive valid inequalities from the diminishing property of k-submodular function, and strengthen them further by imposing an ordering over elements in the defender's …
-
Approximation algorithms for clustering and facility location problems
… worst case approximation algorithms for Uniform Submodular Facility Location (USFL), and Capacitated k-center (CapKCenter) problems. USFL is a generalization of the well-known Uncapacitated Facility Location problem. In USFL the cost of opening a facility is a submodular function of the clients …
-
Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity
… second part, the goal is to derive an objective function considering coverage and motion cost. The objective of search is to maximize the probability of target detection while covering most of the environment in minimum time. The robot needs to consider three objectives: (1) maximal coverage; (2) …
-
Parsimonious, Risk-Aware, and Resilient Multi-Robot Coordination
… in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multi-robot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of …
-
Learning on graphs with high-order relations: spectral methods, optimization and applications
DSpace SAF Submission Ingestion Package generated from Vireo submission #14022 on 2019-11-26 at 12:49:35
-
Layering principles for wireless networks
… at a node are further jointly constrained by a submodular function. While a max-flow min-cut theorem for unicast traffic is known for polymatroidal networks, multiple-unicast traffic has not been studied prior to this work. A key technical contribution of this thesis is an approximate max-flow …
-
Efficient and robust resource allocation for network function virtualization
With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility …