Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBreaking the Quadratic Barrier for Matroid Intersection
87
0
0.0
(
0
)
Added by
Joakim Blikstad
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The matroid intersection problem is a fundamental problem that has been extensively studied for half a century. In the classic version of this problem, we are given two matroids $mathcal{M}_1 = (V, mathcal{I}_1)$ and $mathcal{M}_2 = (V, mathcal{I}_2)$ on a comment ground set $V$ of $n$ elements, and then we have to find the largest common independent set $S in mathcal{I}_1 cap mathcal{I}_2$ by making independence oracle queries of the form Is $S in mathcal{I}_1$? or Is $S in mathcal{I}_2$? for $S subseteq V$. The goal is to minimize the number of queries. Beating the existing $tilde O(n^2)$ bound, known as the quadratic barrier, is an open problem that captures the limits of techniques from two lines of work. The first one is the classic Cunninghams algorithm [SICOMP 1986], whose $tilde O(n^2)$-query implementations were shown by CLS+ [FOCS 2019] and Nguyen [2019]. The other one is the general cutting plane method of Lee, Sidford, and Wong [FOCS 2015]. The only progress towards breaking the quadratic barrier requires either approximation algorithms or a more powerful rank oracle query [CLS+ FOCS 2019]. No exact algorithm with $o(n^2)$ independence queries was known. In this work, we break the quadratic barrier with a randomized algorithm guaranteeing $tilde O(n^{9/5})$ independence queries with high probability, and a deterministic algorithm guaranteeing $tilde O(n^{11/6})$ independence queries. Our key insight is simple and fast algorithms to solve a graph reachability problem that arose in the standard augmenting path framework [Edmonds 1968]. Combining this with previous exact and approximation algorithms leads to our results.
rate research
Read More
We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results.
The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtmans proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+lambda}$ for some fixed, positive $lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that $n > d^{2+lambda}$. This improves the known quadratic lower bounds (e.g. {KdW04, Wood07}). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries, possibly over other fields as well. Our proof introduces several new ideas to existing lower bound techniques, several of which work over every field. At a high level, our proof has two parts, {it clustering} and {it random restriction}. The clustering step uses a powerful theorem of Barthe from convex geometry. It can be used (after preprocessing our LCC to be {it balanced}), to apply a basis change (and rescaling) of the vectors, so that the resulting unit vectors become {it nearly isotropic}. This together with the fact that any LCC must have many `correlated pairs of points, lets us deduce that the vectors must have a surprisingly strong geometric clustering, and hence also combinatorial clustering with respect to the spanning triples. In the restriction step, we devise a new variant of the dimension reduction technique used in previous lower bounds, which is able to take advantage of the combinatorial clustering structure above. The analysis of our random projection method reduces to a simple (weakly) random graph process, and works over any field.
We consider the problem of managing the buffer of a shared-memory switch that transmits packets of unit value. A shared-memory switch consists of an input port, a number of output ports, and a buffer with a specific capacity. In each time step, an arbitrary number of packets arrive at the input port, each packet designated for one output port. Each packet is added to the queue of the respective output port. If the total number of packets exceeds the capacity of the buffer, some packets have to be irrevocably rejected. At the end of each time step, each output port transmits a packet in its queue and the goal is to maximize the number of transmitted packets. The Longest Queue Drop (LQD) online algorithm accepts any arriving packet to the buffer. However, if this results in the buffer exceeding its memory capacity, then LQD drops a packet from the back of whichever queue is currently the longest, breaking ties arbitrarily. The LQD algorithm was first introduced in 1991, and is known to be $2$-competitive since 2001. Although LQD remains the best known online algorithm for the problem and is of great practical interest, determining its true competitiveness is a long-standing open problem. We show that LQD is 1.707-competitive, establishing the first $(2-varepsilon)$ upper bound for the competitive ratio of LQD, for a constant $varepsilon>0$.
In the ordinal Matroid Secretary Problem (MSP), elements from a weighted matroid are presented in random order to an algorithm that must incrementally select a large weight independent set. However, the algorithm can only compare pairs of revealed elements without using its numerical value. An algorithm is $alpha$ probability-competitive if every element from the optimum appears with probability $1/alpha$ in the output. We present a technique to design algorithms with strong probability-competitive ratios, improving the guarantees for almost every matroid class considered in the literature: e.g., we get ratios of 4 for graphic matroids (improving on $2e$ by Korula and Pal [ICALP 2009]) and of 5.19 for laminar matroids (improving on 9.6 by Ma et al. [THEOR COMPUT SYST 2016]). We also obtain new results for superclasses of $k$ column sparse matroids, for hypergraphic matroids, certain gammoids and graph packing matroids, and a $1+O(sqrt{log rho/rho})$ probability-competitive algorithm for uniform matroids of rank $rho$ based on Kleinbergs $1+O(sqrt{1/rho})$ utility-competitive algorithm [SODA 2005] for that class. Our second contribution are algorithms for the ordinal MSP on arbitrary matroids of rank $rho$. We devise an $O(log rho)$ probability-competitive algorithm and an $O(loglog rho)$ ordinal-competitive algorithm, a weaker notion of competitiveness but stronger than the utility variant. These are based on the $O(loglog rho)$ utility-competitive algorithm by Feldman et al.~[SODA 2015].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
