Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userChanging Bases: Multistage Optimization for Matroids and Matchings
378
0
0.0
(
0
)
Added by
Udi Wieder
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper is motivated by the fact that many systems need to be maintained continually while the underlying costs change over time. The challenge is to continually maintain near-optimal solutions to the underlying optimization problems, without creating too much churn in the solution itself. We model this as a multistage combinatorial optimization problem where the input is a sequence of cost functions (one for each time step); while we can change the solution from step to step, we incur an additional cost for every such change. We study the multistage matroid maintenance problem, where we need to maintain a base of a matroid in each time step under the changing cost functions and acquisition costs for adding new elements. The online version of this problem generalizes online paging. E.g., given a graph, we need to maintain a spanning tree $T_t$ at each step: we pay $c_t(T_t)$ for the cost of the tree at time $t$, and also $| T_tsetminus T_{t-1} |$ for the number of edges changed at this step. Our main result is an $O(log m log r)$-approximation, where $m$ is the number of elements/edges and $r$ is the rank of the matroid. We also give an $O(log m)$ approximation for the offline version of the problem. These bounds hold when the acquisition costs are non-uniform, in which caseboth these results are the best possible unless P=NP. We also study the perfect matching version of the problem, where we must maintain a perfect matching at each step under changing cost functions and costs for adding new elements. Surprisingly, the hardness drastically increases: for any constant $epsilon>0$, there is no $O(n^{1-epsilon})$-approximation to the multistage matching maintenance problem, even in the offline case.
rate research
Read More
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most $48$ elements.
In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream then we can never get rid of it, and if we choose not to accept it then we cannot later add it. Babaioff, Immorlica, and Kleinberg [SODA 2007] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g. graphic and transversal matroids). In particular, there is very little known about F-representable matroids (the class of matroids that can be represented as elements of a vector space over a field F), which are one of the foundational matroid classes. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving an O(1)-competitive algorithm for regular matroids (the class of matroids that are representable over every field), and use techniques that are matroid-theoretic rather than graph-theoretic. We use the regular matroid decomposition theorem of Seymour to decompose any regular matroid into matroids which are either graphic, cographic, or isomorphic to R_{10}, and then show how to combine algorithms for these basic classes into an algorithm for regular matroids. This allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids.
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of a matroid $M$, a weight function $omega:E(M)tomathbb{N}$, and integers $kgeq 1, dgeq 0$. The task is to decide if there is a collection of $k$ bases $B_{1}, dotsc, B_{k}$ of $M$ such that the weight of the symmetric difference of any pair of these bases is at least $d$. This is a diverse variant of the classical matroid base packing problem. The input to the Weighted Diverse Common Independent Sets problem consists of two matroids $M_{1},M_{2}$ defined on the same ground set $E$, a weight function $omega:Etomathbb{N}$, and integers $kgeq 1, dgeq 0$. The task is to decide if there is a collection of $k$ common independent sets $I_{1}, dotsc, I_{k}$ of $M_{1}$ and $M_{2}$ such that the weight of the symmetric difference of any pair of these sets is at least $d$. This is motivated by the classical weighted matroid intersection problem. The input to the Diverse Perfect Matchings problem consists of a graph $G$ and integers $kgeq 1, dgeq 0$. The task is to decide if $G$ contains $k$ perfect matchings $M_{1},dotsc,M_{k}$ such that the symmetric difference of any two of these matchings is at least $d$. We show that Weighted Diverse Bases and Weighted Diverse Common Independent Sets are both NP-hard, and derive fixed-parameter tractable (FPT) algorithms for all three problems with $(k,d)$ as the parameter.
In this paper, we consider a multistage expected utility maximization problem where the decision makers utility function at each stage depends on historical data and the information on the true utility function is incomplete. To mitigate the risk arising from ambiguity of the true utility, we propose a maximin robust model where the optimal policy is based on the worst sequence of utility functions from an ambiguity set constructed with partially available information about the decision makers preferences. We then show that the multistage maximin problem is time consistent when the utility functions are state-dependent and demonstrate with a counter example that the time consistency may not be retained when the utility functions are state-independent. With the time consistency, we show the maximin problem can be solved by a recursive formula whereby a one-stage maximin problem is solved at each stage beginning from the last stage. Moreover, we propose two approaches to construct the ambiguity set: a pairwise comparison approach and a $zeta$-ball approach where a ball of utility functions centered at a nominal utility function under $zeta$-metric is considered. To overcome the difficulty arising from solving the infinite dimensional optimization problem in computation of the worst-case expected utility value, we propose piecewise linear approximation of the utility functions and derive error bound for the approximation under moderate conditions. Finally we develop a scenario tree-based computational scheme for solving the multistage preference robust optimization model and report some preliminary numerical results.
A well-known problem in scheduling and approximation algorithms is the Santa Claus problem. Suppose that Santa Claus has a set of gifts, and he wants to distribute them among a set of children so that the least happy child is made as happy as possible. Here, the value that a child $i$ has for a present $j$ is of the form $p_{ij} in { 0,p_j}$. A polynomial time algorithm by Annamalai et al. gives a $12.33$-approximation and is based on a modification of Haxells hypergraph matching argument. In this paper, we introduce a matroid version of the Santa Claus problem. Our algorithm is also based on Haxells augmenting tree, but with the introduction of the matroid structure we solve a more general problem with cleaner methods. Our result can then be used as a blackbox to obtain a $(4+varepsilon)$-approximation for Santa Claus. This factor also compares against a natural, compact LP for Santa Claus.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
