Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDynamic Optimality Refuted -- For Tournament Heaps
113
0
0.0
(
0
)
Added by
Sebastian Wild
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys stored on leaves, and intermediate nodes tracking the min of their respective subtrees. They represent a natural starting point for studying self-adjusting heaps due to the need to access the root-to-leaf path upon modifications. We combine previous studies on the competitive ratios of unordered binary search trees by [Fredman WADS2011] and on order-by-next request by [Martinez-Roura TCS2000] and [Munro ESA2000] to show that for any number of fingers, tournament heaps cannot handle a sequence of modify-key operations with competitive ratio in $o(sqrt{log{n}})$. Critical to this analysis is the characterization of the modifications that a heap can undergo upon an access. There are $exp(Theta(n log{n}))$ valid heaps on $n$ keys, but only $exp(Theta(n))$ binary search trees. We parameterize the modification power through the well-studied concept of fingers: additional pointers the data structure can manipulate arbitrarily. Here we demonstrate that fingers can be significantly more powerful than servers moving on a static tree by showing that access to $k$ fingers allow an offline algorithm to handle any access sequence with amortized cost $O(log_{k}(n) + 2^{lg^{*}n})$.
rate research
Read More
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence $X in [n]^m$. Both bounds play a central role in the ongoing pursuit of the dynamic optimality conjecture (Sleator and Tarjan, 1985), but their relationship remained unknown for more than three decades. We show that Wilbers Funnel bound dominates his Alternation bound for all $X$, and give a tight $Theta(lglg n)$ separation for some $X$, answering Wilbers conjecture and an open problem of Iacono, Demaine et. al. The main ingredient of the proof is a new symmetric characterization of Wilbers Funnel bound, which proves that it is invariant under rotations of $X$. We use this characterization to provide initial indication that the Funnel bound matches the Independent Rectangle bound (Demaine et al., 2009), by proving that when the Funnel bound is constant, $mathsf{IRB}_{diaguphspace{-.6em}square}$ is linear. To the best of our knowledge, our results provide the first progress on Wilbers conjecture that the Funnel bound is dynamically optimal (1986).
In this paper we present a new data structure for double ended priority queue, called min-max fine heap, which combines the techniques used in fine heap and traditional min-max heap. The standard operations on this proposed structure are also presented, and their analysis indicates that the new structure outperforms the traditional one.
With an exploding global market and the recent introduction of online cash prize tournaments, fantasy sports contests are quickly becoming a central part of the social gaming and sports industries. For sports fans and online media companies, fantasy sports contests are an opportunity for large financial gains. However, they present a host of technical challenges that arise from the complexities involved in running a web-scale, prize driven fantasy sports platform. We initiate the study of these challenges by examining one concrete problem in particular: how to algorithmically generate contest payout structures that are 1) economically motivating and appealing to contestants and 2) reasonably structured and succinctly representable. We formalize this problem and present a general two-staged approach for producing satisfying payout structures given constraints on contest size, entry fee, prize bucketing, etc. We then propose and evaluate several potential algorithms for solving the payout problem efficiently, including methods based on dynamic programming, integer programming, and heuristic techniques. Experimental results show that a carefully designed heuristic scales very well, even to contests with over 100,000 prize winners. Our approach extends beyond fantasy sports -- it is suitable for generating engaging payout structures for any contest with a large number of entrants and a large number of prize winners, including other massive online games, poker tournaments, and real-life sports tournaments.
We show the $O(log n)$ time extract minimum function of efficient priority queues can be generalized to the extraction of the $k$ smallest elements in $O(k log(n/k))$ time, where we define $log(x)$ as $max(log_2(x), 1)$. We first show heap-ordered tree selection (Kaplan et al., SOSA 19) can be applied on the heap-ordered trees of the classic Fibonacci heap to support the extraction in $O(k log(n/k))$ amortized time. We then show selection is possible in a priority queue with optimal worst-case guarantees by applying heap-ordered tree selection on Brodal queues (SODA 96), supporting the operation in $O(k log(n/k))$ worst-case time. Via a reduction from the multiple selection problem, $Omega(k log(n/k))$ time is necessary if insertion is supported in $o(log n)$ time. We then apply the result to lazy search trees (Sandlund & Wild, FOCS 20), creating a new interval data structure based on selectable heaps. This gives optimal $O(B+n)$ time lazy search tree performance, lowering insertion complexity into a gap $Delta_i$ to $O(log(n/|Delta_i|))$ time. An $O(1)$ time merge operation is also made possible when used as a priority queue, among other situations. If Brodal queues are used, runtimes of the lazy search tree can be made worst-case in the general case of two-sided gaps. The presented data structure makes fundamental use of soft heaps (Chazelle, J. ACM 00), biased search trees, and efficient priority queues, approaching the theoretically-best data structure for ordered data.
In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given $m times n$ matrix $A$ and an $m$-vector $b=(b_1,dots, b_m)$, there is a non-negative integer $n$-vector $x$ such that $Ax=b$. Solving (IP) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IP) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ArXiv 2018]. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal. We also show that when the matrix $A$ is assumed to be non-negative, a component of Papadimitrious original algorithm is already nearly optimal under ETH. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IP) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IP) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IP) when the path-width of the corresponding column-matroid is a constant.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
