AlgOrEsEArch

### AlgOrEsEArch

• provides expertise and consulting service in algorithm design and analysis

• provides collaboration on research projects in the area of algorithms

• provides tailored solutions for specific algorithmic problems

Founded by Adrian Dumitrescu: a computer scientist and mathematician with expertise in the fields of theory of algorithms, combinatorics, and discrete and computational geometry. Adrian Dumitrescu holds a PhD in Computer Science from Rutgers University and is an author of about 250 academic papers and a recent book on algorithmic problems and exercises. More details can be found here.

Email us your proposal at contact@algoresearch.org

### Books

1. Adrian Dumitrescu and Ke Chen, The Ape Book: Algorithmic Problems and Exercises, ISBN: 9798674163009, August 2020. (Available at amazon.com)

### Papers

1. Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot, On convex polygons in Cartesian products, Journal of Computational Geometry, 11(2), 2020, 205-233. Preprint available on arXiv.

2. Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth, On the stretch factor of polygonal chains, SIAM Journal on Discrete Mathematics, 35(3), 2021, 1592-1614.

3. Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth, Sparse hop spanners for unit disk graphs, Computational Geometry: Theory and Applications, 100: 101808, (2022). A preliminary version in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), December 14-18, 2020, Hong Kong, China (Virtual Conference), Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl, vol. 181, pp. 57:1-57:17. Preprint available on arXiv.

4. Adrian Dumitrescu, Finding triangles or independent sets, manuscript, 2021. Preprint available on arXiv.

5. Adrian Dumitrescu and Josef Tkadlec, Piercing all translates of a set of axis-parallel rectangles, Proceedings of the 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021), Ottawa, Canada, July 2021, Vol. 12757 of LNCS, pp. 295-309, Springer, 2021. Preprint available on arXiv.

6. Adrian Dumitrescu and Josef Tkadlec, Lattice and non-lattice piercing of axis-parallel rectangles: exact algorithms and a separation result, manuscript, 2022. Preprint available on arXiv.

7. Adrian Dumitrescu, The Dirac-Goodman-Pollack conjecture, manuscript, 2022. Preprint available on arXiv.

8. Adrian Dumitrescu and Csaba D. Tóth, Finding points in convex position in density-restricted sets, manuscript, 2022. Preprint available on arXiv.

### Open Problems

Topics: exact algorithms, approximation algorithms, randomized algorithms, discrete and computational geometry, etc. Each problem is labeled by the proposer and/or the owner of the current best result. For brevity, in what follows we write "argue that none exists" instead of "argue that none exists within a reasonable framework."

• [Knuth:] Let $$S(n)$$ be the minimum number of comparisons that will suffice to sort $$n$$ elements. Determine the exact value of $$S(n)$$ for infinitely many $$n$$.  See also here (Vol. 3, Ch. 5) .

• [Aigner (for (i):] Let $$V_i(n)$$ be the minimum number of comparisons needed in the worst case to select the $$i$$-th smallest element from $$n$$ elements.
(i) Let $$i < n/2$$. Prove or disprove that $$V_i(n) \leq V_{i+1}(n)$$.  See also here.
(ii) Prove or disprove that $$V_7(16) =30$$.
(iii) Prove or disprove that $$V_6(17) =31$$.
(iv) Prove or disprove that $$V_4(19) =29$$.

• [Paterson:] Conjecture. The worst-case number of comparisons required to find the median of $$n$$ elements is asymptotic to $$n \log_{4/3} 2 \sim 2.4094\ldots n.$$  See also here.

• [Kislitsyn:] "$$1/3$$ - $$2/3$$ Conjecture"  For every poset that is not a chain, there is some pair of elements $$x$$ and $$y$$ so that $$x$$ appears above $$y$$ in a random linear extension of the poset at least $$1/3$$ of the time and at most $$2/3$$ of the time.  See also here.

• [Berlekamp:] Can $$X + Y$$ sorting be done in $$o(n^2 \log{n})$$ time?  See also here.

• [Woeginger:] In the SUBSET-SUM problem, given $$n$$ positive integers $$a_1,\ldots,a_n$$ and a target sum $$t$$, the problem is to decide whether there exists some subset of the $$a_i$$ that add up to $$t$$. (SUBSET-SUM is known to be NP-hard.)  See also here.
(a) Construct an $$O(1.4^n)$$-time algorithm for SUBSET-SUM or argue that none exists.
(b) Construct an $$O(1.99^n)$$-time and polynomial space algorithm for SUBSET-SUM or argue that none exists.

• [Woeginger:] The standard CLIQUE problem asks to find a clique of maximum size in a given graph $$G=(V,E)$$. Let $$|V|=n, |E|=m$$.  See also here.
Construct an exact algorithm for CLIQUE with time complexity $$O(1.1^n)$$ or argue that none exists.

• (folklore) What is the algorithmic complexity of the minimum spanning tree problem?  See also here.

• (folklore) Can integer factorization be done in polynomial time?  See also here.

• (folklore) The 3SUM problem asks if a given set of $$n$$ real numbers contains three elements that sum to zero. Can this problem be solved in strongly sub-quadratic time, that is, in time $$O(n^{2-\varepsilon})$$ for some constant $$\varepsilon>0$$ ? How about INTEGER 3SUM, where each entry is an integer whose absolute value is, say, at most $$n^3$$?  See also here.

• (folklore) Prove or disprove: Given $$n$$ points in the plane, no three of which are collinear, it can be determined in $$O(n)$$ time if they are in convex position. It is conjectured that the answer is negative. See also here.

• [Gonzalez:] In the Euclidean $$k$$-center problem, given a set of $$n$$ points in the Euclidean space and a positive integer $$k$$, the problem is to cover the set by $$k$$ congruent balls centered at the points so that the diameter of the balls is minimized. A factor $$2$$ approximation algorithm is available.  See also here.
Provide a ratio $$1.99$$ approximation for $$k$$-center in the plane or argue that none exists.

• [Christofides:] Christofides' algorithm for the metric traveling salesman problem is a $$3/2$$-approximation algorithm. Provide a $$1.49$$-approximation algorithm or argue that none exists.  See also here (Ch. 17).

• [Dumitrescu, Tóth:] Is there a constant-factor approximation algorithm for TSP with convex bodies in the plane? (or for MST with convex bodies in the plane)?  See also here (p. 375).

• [Dumitrescu, Tóth:] Is TSP with disks in the plane APX-hard? Is TSP with convex bodies in the plane APX-hard?  See also here (p. 375).

• [Fekete:] Is the MAX TSP NP-hard in the Euclidean plane? What if the tour is required to be noncrossing?  See also here (Ch. 31).

• [Alon, Rajagopalan, Suri:] Let $$S$$ be a set of $$n$$ points in the plane (say, with no three points collinear). What is the computational complexity of the following problems?
(i) Compute a longest non-crossing spanning tree.
(ii) Compute a longest non-crossing perfect matching ($$n$$: even).
(iii) Compute a longest non-crossing hamiltonian path (or cycle).

• (folklore) Does every finite set of points in the plane admit a plane geometric graph whose vertex set is the given set of points that has maximum degree three and whose Euclidean stretch factor is bounded from above by a constant?  See also here (Problem 15).

• [Williamson and Shmoys:] Devise a polynomial-time algorithm that uses $$O(\log^c{n})$$ colors for a $$3$$-colorable graph, or argue that none exists.  See also here (Ch. 17).

• [Vazirani:] Provide a factor $$0.51$$ approximation algorithm for the following problem or argue that none exists. Given a directed graph $$G=(V,E)$$, pick a subset of edges from $$E$$ of maximum size so that the resulting subgraph is acyclic.  See also here (p. 7).

• (folklore) Give a polynomial-time algorithm for computing a constant-factor approximation of the minimum number of point guards needed to cover a simple polygon or argue that none exists.  See also here (Ch. 30).

• Knuth: Prove or disprove that the number of isomorphism classes of simple pseudoline arrangements is $$2^{{n \choose 2} + o(n^2)}$$.  See also here (Ch. 5).

• (folklore) What is the maximum complexity of the $$k$$-level in an arrangement of $$n$$ lines in the plane?  See also here (Ch. 28).

• [Kára, Pór, Wood:] Does there exist for every $$k$$ a number $$n = n(k)$$ such that in any set $$P$$ of $$n$$ points in the plane there are $$k$$ elements that are either collinear or pairwise see each other? (Two elements of $$P$$ see each other if the segment connecting them does not pass through any other point of $$P$$.)  See also here.

• [Erdős, Szekeres:] Do every $$2^{n-2} + 1$$ points in the plane (no 3 collinear) determine a convex $$n$$-gon?  See also here.

• [Larman, Matoušek, Pach, Töröcsik:] What is the largest positive number $$f=f(n)$$ such that any family of $$n$$ convex bodies in the plane has a subfamily of $$f$$ members that are either pairwise disjoint or pairwise intersecting? It is known that $$n^{0.2} \leq f(n) \leq n^{0.4207}$$.  See also here (Ch. 10).

• (folklore) Does every familiy of $$n$$ axis-parallel rectangles in the plane contain a subfamily of $$\Omega(\sqrt{n})$$ members that are either pairwise disjoint or pairwise intersecting? It is known that one can find a subfamily of size $$\Omega(\sqrt{n/\log{n}})$$.  See also here (Ch. 9).

• [Pach, Tardos:] Let $$S$$ be a set of $$n$$ disjoint axis-aligned rectangles in the plane. Prove or disprove that there exists a BSP that separates $$c n$$ members of $$S$$ (without being fragmented by the cuts), for some positive constant $$c>0$$.  See also here.

• [Dumitrescu, Jiang:] Given an axis-parallel rectangle $$U$$ in the plane containing $$n$$ points, the problem of computing a maximum-area axis-parallel empty rectangle contained in $$U$$ is one of the oldest in computational geometry. Prove or disprove that the number of maximum-area empty rectangles amidst $$n$$ points in the plane is $$O(n)$$.  See also here.