Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiverse Collections in Matroids and Graphs
151
0
0.0
(
0
)
Added by
Geevarghese Philip
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Sparse graphs and their associated matroids play an important role in rigidity theory, where they capture the combinatorics of generically rigid structures. We define a new family called {bf graded sparse graphs}, arising from generically pinned (completely immobilized) bar-and-joint frameworks and prove that they also form matroids. We address five problems on graded sparse graphs: {bf Decision}, {bf Extraction}, {bf Components}, {bf Optimization}, and {bf Extension}. We extend our {bf pebble game algorithms} to solve them.
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $lceil frac{n}{2} rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Haggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
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.
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.
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
