Spelling suggestions: "subject:"submodular maximization"" "subject:"submodular maximizations""
1 
Oblivious and Nonoblivious Local Search for Combinatorial OptimizationWard, Justin 07 January 2013 (has links)
Standard local search algorithms for combinatorial optimization problems repeatedly apply small changes to a current solution to improve the problem's given objective function. In contrast, nonoblivious 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 nonoblivious approaches for a variety of problems, and derive new, improved nonoblivious local search algorithms for several problems in the area of constrained linear and monotone submodular maximization.
First, we give a new, randomized approximation algorithm for maximizing a monotone submodular function subject to a matroid constraint. Our algorithm's approximation ratio matches both the known hardness of approximation bounds for the problem and the performance of the recent ``continuous greedy'' algorithm. Unlike the continuous greedy algorithm, our algorithm is straightforward and combinatorial. In the case that the monotone submodular function is a coverage function, we can obtain a further simplified, deterministic algorithm with improved running time.
Moving beyond the case of single matroid constraints, we then consider general classes of set systems that capture problems that can be approximated well. While previous such classes have focused primarily on greedy algorithms, we give a new class that captures problems amenable to optimization by local search algorithms. We show that several combinatorial optimization problems can be placed in this class, and give a nonoblivious local search algorithm that delivers improved approximations for a variety of specific problems.
In contrast, we show that standard local search algorithms give no improvement over known approximation results for these problems, even when allowed to search larger neighborhoods than their nonoblivious counterparts.
Finally, we expand on these results by considering standard local search algorithms for constraint satisfaction problems. We develop conditions under which the approximation ratio of standard local search remains limited even for superpolynomial or exponential local neighborhoods. In the special case of MaxCut, we further show that a variety of techniques including random or greedy initialization, large neighborhoods, and bestimprovement pivot rules cannot improve the approximation performance of standard local search.

2 
Oblivious and Nonoblivious Local Search for Combinatorial OptimizationWard, Justin 07 January 2013 (has links)
Standard local search algorithms for combinatorial optimization problems repeatedly apply small changes to a current solution to improve the problem's given objective function. In contrast, nonoblivious 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 nonoblivious approaches for a variety of problems, and derive new, improved nonoblivious local search algorithms for several problems in the area of constrained linear and monotone submodular maximization.
First, we give a new, randomized approximation algorithm for maximizing a monotone submodular function subject to a matroid constraint. Our algorithm's approximation ratio matches both the known hardness of approximation bounds for the problem and the performance of the recent ``continuous greedy'' algorithm. Unlike the continuous greedy algorithm, our algorithm is straightforward and combinatorial. In the case that the monotone submodular function is a coverage function, we can obtain a further simplified, deterministic algorithm with improved running time.
Moving beyond the case of single matroid constraints, we then consider general classes of set systems that capture problems that can be approximated well. While previous such classes have focused primarily on greedy algorithms, we give a new class that captures problems amenable to optimization by local search algorithms. We show that several combinatorial optimization problems can be placed in this class, and give a nonoblivious local search algorithm that delivers improved approximations for a variety of specific problems.
In contrast, we show that standard local search algorithms give no improvement over known approximation results for these problems, even when allowed to search larger neighborhoods than their nonoblivious counterparts.
Finally, we expand on these results by considering standard local search algorithms for constraint satisfaction problems. We develop conditions under which the approximation ratio of standard local search remains limited even for superpolynomial or exponential local neighborhoods. In the special case of MaxCut, we further show that a variety of techniques including random or greedy initialization, large neighborhoods, and bestimprovement pivot rules cannot improve the approximation performance of standard local search.

3 
Parsimonious, RiskAware, and Resilient MultiRobot CoordinationZhou, Lifeng 28 May 2020 (has links)
In this dissertation, we study multirobot coordination in the context of multitarget tracking. Specifically, we are interested in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multirobot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of robots assigned increases. The advantage of formulating coordination problems as submodular optimization is that a simple, greedy algorithm is guaranteed to give a good performance. However, often this comes at the expense of unrealistic models and assumptions. For example, the standard formulation does not take into account the fact that robots may fail, either randomly or due to adversarial attacks. When operating in uncertain conditions, we typically seek to optimize the expected performance. However, this does not give any flexibility for a user to seek conservative or aggressive behaviors from the team of robots. Furthermore, most coordination algorithms force robots to communicate at each time step, even though they may not need to. Our goal in this dissertation is to overcome these limitations by devising coordination algorithms that are parsimonious in communication, allow a user to manage the risk of the robot performance, and are resilient to worstcase robot failures and attacks.
In the first part of this dissertation, we focus on designing parsimonious communication strategies for target tracking. Specifically, we investigate the problem of determining when to communicate and who to communicate with. When the robots use range sensors, the tracking performance is a function of the relative positions of the robots and the targets. We propose a selftriggered communication strategy in which a robot communicates its own position with its neighbors only when a certain set of conditions are violated. We prove that this strategy converges to the optimal robot positions for tracking a single target and in practice, reduces the number of communication messages by 30%. When tracking multiple targets, we can reduce the communication by forming subsets of robots and assigning one subset to track a target. We investigate a number of measures for tracking quality based on the observability matrix and show which ones are submodular and which ones are not. For nonsubmodular measures, we show a greedy algorithm gives a 1/(n+1) approximation, if we restrict the subset to n robots.
In optimizing submodular functions, a common assumption is that the function value is deterministic, which may not hold in practice. For example, the sensor performance may depend on environmental conditions which are not known exactly. In the second part of the dissertation, we design an algorithm for stochastic submodular optimization. The standard formulation for stochastic optimization optimizes the expected performance. However, the expectation is a riskneutral measure. Instead, we optimize the Conditional ValueatRisk (CVaR), which allows the user the flexibility of choosing a risk level. We present an algorithm, based on the greedy algorithm, and prove that its performance has bounded suboptimality and improves with running time. We also present an online version of the algorithm to adapt to realtime scenarios.
In the third part of this dissertation, we focus on scenarios where a set of robots may fail naturally or due to adversarial attacks. Our objective is to track as many targets as possible, a submodular measure, assuming worstcase robot failures. We present both centralized and distributed resilient tracking algorithms to cope with centralized and distributed communication settings. We prove these algorithms give a constantfactor approximation of the optimal in polynomial running time. / Doctor of Philosophy / Today, robotics and autonomous systems have been increasingly used in various areas such as manufacturing, military, agriculture, medical sciences, and environmental monitoring. However, most of these systems are fragile and vulnerable to adversarial attacks and uncertain environmental conditions. In most cases, even if a part of the system fails, the entire system performance can be significantly undermined. As robots start to coexist with humans, we need algorithms that can be trusted under realworld, not just ideal conditions. Thus, this dissertation focuses on enabling security, trustworthiness, and longterm autonomy in robotics and autonomous systems. In particular, we devise coordination algorithms that are resilient to attacks, trustworthy in the face of the uncertain conditions, and allow the longterm operation of multirobot systems. We evaluate our algorithms through extensive simulations and proofofconcept experiments. Generally speaking, multirobot systems form the "physical" layer of CyberPhysical Sytems (CPS), the Internet of Things (IoT), and Smart City. Thus, our research can find applications in the areas of connected and autonomous vehicles, intelligent transportation, communications and sensor networks, and environmental monitoring in smart cities.

4 
Submodular Order Maximization Subject to a pMatchoid Constraint / Submodulär ordermaximering som är föremål för ett pmatchoidbegränsningsvillkorWu, Yizhan January 2022 (has links)
Recently, Udwani defined a new class of set functions under monotonicity and subadditivity, called submodular order functions, which is a subfamily of submodular functions. Informally, the submodular order function admits a very limited form of submodularity which is defined over a specific permutation of the ground set. His work pointed out the intriguing connection between streaming submodular maximization and submodular order maximization. Inspired by a 0.25approximation streaming algorithm for maximizing a monotone submodular function subject to a matroid constraint, Udwani gave a 0.25approximation algorithm for submodular order functions maximization subject to a matroid constraint. Based on the above results, we would like to explore further in which cases it is feasible to generalize from streaming submodular maximization algorithms to submodular order maximization algorithms. As a more general constraint than matroid, pmatchoid is a collection of p matroids with each matroid defined on some subsets of the ground set. Related work gave a 1/4papproximation streaming algorithm for monotone submodular functions maximization under a pmatchoid constraint. Inspired by the above algorithms and the intriguing connection, we used some techniques to try to generalize several streaming algorithms for submodular functions to the offline algorithms for submodular order functions, including interleaved partitions and incremental values. Assuming that the objective function f is subadditive and nonnegative, we gave a 1/4papproximation algorithm for monotone submodular order maximization to a pmatchoid constraint. In addition, we summarize the failures of other cases. / Nyligen definierade Udwani en ny klass av mängdfunktioner under monotonicitet och subadditivitet, som kallas submodulära ordningsfunktioner och som är en underfamilj av submodulära funktioner. Informellt sett medger den submodulära ordningsfunktionen en mycket begränsad form av submodularitet som är definierad över en specifik permutation av grundmängden. Hans arbete pekade på det spännande sambandet mellan strömmande submodulär maximering och submodulär ordermaximering. Inspirerad av en strömningsalgoritm med 0.25approximation för maximering av en monoton submodulär funktion som är föremål för en matroidbegränsning, gav Udwani en algoritm med 0.25approximation för maximering av submodulära ordningsfunktioner som är föremål för en matroidbegränsning. Baserat på ovanstående resultat skulle vi vilja utforska ytterligare i vilka fall det är möjligt att generalisera från algoritmer för strömning av submodulära maximeringsfunktioner till algoritmer för maximering av submodulära orderfunktioner. Som en mer allmän begränsning än matroid är pmatchoid en samling av p matroider där varje matroid definieras på vissa delmängder av grundmängden. Relaterade arbeten gav en strömmingsalgoritm med 1/4ptillnärmning för monoton submodulär funktionsmaximering under en pmatchoidbegränsning. Inspirerade av ovanstående algoritmer och det spännande sambandet använde vi vissa tekniker för att försöka generalisera flera strömningsalgoritmer för submodulära funktioner till offlinealgoritmer för submodulära ordningsfunktioner, inklusive interleaved partitions och inkrementella värden. Under förutsättning att målfunktionen f är subadditiv och ickenegativ gav vi en algoritm för 1/4ptillnärmning för monoton submodulär ordermaximering till ett pmatchoidbegränsningsvillkor. Dessutom sammanfattar vi misslyckanden i andra fall.

Page generated in 0.1332 seconds