Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBreaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
344
0
0.0
(
0
)
Added by
Pavel Vesel\\'y
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
We discuss the problem of constructing differential operators for the generalized IBP reduction algorithms at the 2-loop level. A deeply optimized software allows one to efficiently construct such operators for the first non-degenerate 2-loop cases. The most efficient approach is found to be via the so-called partial operators that are much simpler than the complete ones, and that affect the power of only one of the polynomials in the product.
The {em longest common subsequence (LCS)} problem is a classic and well-studied problem in computer science. LCS is a central problem in stringology and finds broad applications in text compression, error-detecting codes and biological sequence comparison. However, in numerous contexts, words represent cyclic sequences of symbols and LCS must be generalized to consider all circular shifts of the strings. This occurs especially in computational biology when genetic material is sequenced form circular DNA or RNA molecules. This initiates the problem of {em longest common cyclic subsequence (LCCS)} which finds the longest subsequence between all circular shifts of two strings. In this paper, we give an $O(n^2)$ algorithm for solving LCCS problem where $n$ is the number of symbols in the strings.
At CPM 2017, Castelli et al. define and study a new variant of the Longest Common Subsequence Problem, termed the Longest Filled Common Subsequence Problem (LFCS). For the LFCS problem, the input consists of two strings $A$ and $B$ and a multiset of characters $mathcal{M}$. The goal is to insert the characters from $mathcal{M}$ into the string $B$, thus obtaining a new string $B^*$, such that the Longest Common Subsequence (LCS) between $A$ and $B^*$ is maximized. Casteli et al. show that the problem is NP-hard and provide a 3/5-approximation algorithm for the problem. In this paper we study the problem from the experimental point of view. We introduce, implement and test new heuristic algorithms and compare them with the approximation algorithm of Casteli et al. Moreover, we introduce an Integer Linear Program (ILP) model for the problem and we use the state of the art ILP solver, Gurobi, to obtain exact solution for moderate sized instances.
In this work, we consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s1 and s2 over an alphabet A, a set C_s of strings, and a function Co from A to N, the DC-LCS problem consists in finding the longest subsequence s of s1 and s2 such that s is a supersequence of all the strings in Cs and such that the number of occurrences in s of each symbol a in A is upper bounded by Co(a). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem: the Constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution. Secondly, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings and the size of the alphabet A. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
