1,721,031 research outputs found
New Binary Search Tree Bounds via Geometric Inversions
Get PDFThe long-standing dynamic optimality conjecture postulates the existence of a dynamic binary search tree (BST) that is O(1)-competitive to all other dynamic BSTs. Despite attempts from many groups of researchers, we believe the conjecture is still far-fetched. One of the main reasons is the lack of the "right" potential functions for the problem: existing results that prove various consequences of dynamic optimality rely on very different potential function techniques, while proving dynamic optimality requires a single potential function that can be used to derive all these consequences. In this paper, we propose a new potential function, that we call extended (geometric) inversion. Inversion is arguably the most natural potential function principle that has been used in competitive analysis but has never been used in the context of BSTs. We use our potential function to derive new results, as well as streamlining/strengthening existing results.
First, we show that a broad class of BST algorithms (including Greedy and Splay) are O(1)-competitive to Move-to-Root algorithm and therefore have simulation embedding property - a new BST property that was recently introduced and studied by Levy and Tarjan (SODA 2019). This result, besides substantially expanding the list of BST algorithms having this property, gives the first potential function proof of the simulation embedding property for BSTs (thus unifying apparently different kinds of results). Moreover, our analysis is the first where the costs of two dynamic binary search trees are compared against each other directly and systematically. Secondly, we use our new potential function to unify and strengthen known BST bounds, e.g., showing that Greedy satisfies the weighted dynamic finger property within a multiplicative factor of (5+o(1))
Pinning down the Strong Wilber 1 Bound for Binary Search Trees
Get PDFThe dynamic optimality conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known O(log log n)-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an O(log log n)-approximation, even in the offline setting. All known non-trivial algorithms for BST’s so far rely on comparing the algorithm’s cost with the so-called Wilber’s first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right.
Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as Ω(log log n/ log log log n); in fact, we show that the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer D > 0, obtains an O(D)-approximation in time exp (O (n^{1/2^{Ω(D)}}log n)). In particular, this yields a constant-factor approximation algorithm with sub-exponential running time. Moreover, we obtain a simpler and cleaner efficient O(log log n)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis
Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
No full text| openaire: EC/H2020/759557/EU//ALGOComDynamic Optimality Conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. The conjecture remains wide open, despite extensive work and some notable progress, including, for example, the O(loglogn)-competitive Tango Trees, which is the best currently known competitive ratio. One of the main hurdles towards settling the conjecture is that we currently do not have polynomial-time approximation algorithms achieving better than an O(loglogn)-approximation, even in the offline setting. All known non-trivial algorithms for BSTs rely on comparing the algorithm's cost with the so-called Wilber-1 bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is twofold. First, we show that the gap between WB-1 and the optimal solution value can be as large as Ω(loglogn/logloglogn) ; in fact, we show that the gap holds even for several stronger variants of the bound.∗ Second, we show, given an integer D>0, a D-approximation algorithm that runs in time exp(O(n1/2Ω(D)logn)). In particular, this yields a constant-factor approximation algorithm with subexponential running time.∗∗ Moreover, we obtain a simpler and cleaner efficient O(loglogn)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis.Peer reviewe
On Finding Balanced Bicliques via Matchings
No full text| openaire: EC/H2020/759557/EU//ALGOComIn the Maximum Balanced Biclique Problem (MBB), we are given an n-vertex graph G= (V, E), and the goal is to find a balanced complete bipartite subgraph with q vertices on each side while maximizing q. The MBB problem is among the first known NP-hard problems, and has recently been shown to be NP-hard to approximate within a factor n1 - o ( 1 ), assuming the Small Set Expansion hypothesis [Manurangsi, ICALP 2017]. An O(n/ log n) approximation follows from a simple brute-force enumeration argument. In this paper, we provide the first approximation guarantees beyond brute-force: (1) an O(n/ log 2n) efficient approximation algorithm, and (2) a parameterized approximation that returns, for any r∈ N, an r-approximation algorithm in time exp(O(nrlogr)). To obtain these results, we translate the subgraph removal arguments of [Feige, SIDMA 2004] from the context of finding a clique into one of finding a balanced biclique. The key to our proof is the use of matching edges to guide the search for a balanced biclique.Peer reviewe
Coloring and maximum weight independent set of rectangles
No full text| openaire: EC/H2020/759557/EU//ALGOComIn 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an O(ω2)-coloring, where ω is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is O(ω log ω)-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time O(log log n)-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of O(logloglognn).Peer reviewe
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
Get PDFA cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges.
Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Get PDFGreedy BST (or simply Greedy) is an online self-adjusting binary search tree
defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon,
Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan
1985), Greedy is considered the most promising candidate for being dynamically
optimal, i.e., starting with any initial tree, their access costs on any
sequence is conjectured to be within factor of the offline optimal.
However, in the past four decades, the question has remained elusive even for
highly restricted input.
In this paper, we prove new bounds on the cost of Greedy in the ''pattern
avoidance'' regime. Our new results include:
The (preorder) traversal conjecture for Greedy holds up to a factor of
, improving upon the bound of in
(Chalermsook et al., FOCS 2015). This is the best known bound obtained by any
online BSTs.
We settle the postorder traversal conjecture for Greedy.
The deque conjecture for Greedy holds up to a factor of ,
improving upon the bound in (Chalermsook, et al., WADS
2015).
The split conjecture holds for Greedy up to a factor of .
Key to all these results is to partition (based on the input structures) the
execution log of Greedy into several simpler-to-analyze subsets for which
classical forbidden submatrix bounds can be leveraged. Finally, we show the
applicability of this technique to handle a class of increasingly complex
pattern-avoiding input sequences, called -increasing sequences.
As a bonus, we discover a new class of permutation matrices whose extremal
bounds are polynomially bounded. This gives a partial progress on an open
question by Jacob Fox (2013).Comment: Accepted to SODA 202
Scheduling with Machine Conflicts
No full textWe study the scheduling problem of makespan minimization with machine conflicts that arise in various settings, e.g., shared resources for pre- and post-processing of tasks or spatial restrictions. In this context, each job has a blocking time before and after its processing time, i.e., three parameters. Given a set of jobs, a set of machines, and a graph representing machine conflicts, the problem SchedulingWithMachineConflicts (smc), asks for a conflict-free schedule of minimum makespan in which the blocking times of no two jobs intersect on conflicting machines. We show that, unless P = NP, smc on m machines does not allow for a O(m1-e) -approximation algorithm for any e> 0, even in the case of identical jobs and every choice of fixed positive parameters, including the unit case. Complementary, we provide approximation algorithms when a suitable collection of independent sets is given. Finally, we present polynomial time algorithms to solve the problem for the case of unit jobs smc-Unit on special graph classes. As our main result, we solve smc-Unit for bipartite graphs by using structural insights for conflict graphs of star forests. As the set of active machines at each point in time induces a bipartite graph, the insights yield a local optimality criterion
Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
Get PDFEn teoría de grafos, el problema de encontrar el conjunto independiente máximo (MIS, por sus siglas en inglés), y el problema de encontrar el conjunto de golpe mínimo (MHS), son de vital relevancia en el campo de estudi. En cuanto a la complejidad computacional, ambos son NP difíciles (incluso de aproximación) para grafos en general. En esta tesina, nos centramos en las familias de grafos de rectángulos, cuadrados y de ganchos, que son entradas más simples para esta problemática. Estudiamos, asimismo, algunos problemas combinatorios extremales, y analizamos de qué manera pueden utilizarse para obtener algoritmos de aproximación para MIS y MHS en estas clases de grafos
Knapsack secretary through boosting
No full textWe revisit the knapsack-secretary problem (Babaioff et al.; APPROX 2007), a generalization of the classic secretary problem in which items have different sizes and multiple items may be selected if their total size does not exceed the capacity B of a knapsack. Previous works show competitive ratios of 1/(10e) (Babaioff et al.), 1/8.06 (Kesselheim et al.; STOC 2014), and 1/6.65 (Albers, Khan, and Ladewig; APPROX 2019) for the general problem but no definitive answers for the achievable competitive ratio; the best known impossibility remains 1/e as inherited from the classic secretary problem. In an effort to make more qualitative progress, we take an orthogonal approach and give definitive answers for special cases. Our main result is on the 1-2-knapsack secretary problem, the special case in which B= 2 and all items have sizes 1 or 2, arguably the simplest meaningful generalization of the secretary problem towards the knapsack secretary problem. Our algorithm is simple: It boosts the value of size-1 items by a factor α&gt; 1 and then uses the size-oblivious approach by Albers, Khan, and Ladewig. We show by a nontrivial analysis that this algorithm achieves a competitive ratio of 1/e if and only if 1.40 ≲ α≤ e/ (e- 1 ) ≈ 1.58. Towards understanding the general case, we then consider the case when sizes are 1 and B, and B is large. While it remains unclear if 1/e can be achieved in that case, we show that algorithms based only on the relative ranks of the item values can achieve precisely a competitive ratio of 1 / (e+ 1 ). To show the impossibility, we use a non-trivial generalization of the factor-revealing linear program for the secretary problem (Buchbinder, Jain, and Singh; IPCO 2010).</p
- …
