The minimum convex cover problem seeks to cover a polygon \(P\) with the fewest convex polygons that lie within \(P\). This problem is \(\exists\mathbb{R}\)-complete, and the best previously known algorithm, due to Eidenbenz and Widmayer (2001), achieves an \(O(\log n)\)-approximation in \(O(n^{29} \log n)\) time, where \(n\) is the complexity of \(P\).

In the fast-evolving world of wireless networks, achieving high throughput with low latency is essential for future communication systems. Although low-complexity OSPF-type solutions are effective in lightly-loaded networks, their performance tends to degrade as congestion increases. Recent methods have proposed using backpressure and deep learning for route optimization, but these approaches face challenges due to their high implementation and computational complexity, which may exceed the capabilities of networks with limited hardware resources. A key challenge is developing algorithms that improve throughput and reduce latency while keeping complexity levels compatible with OSPF. In this paper, we address this challenge by developing a novel approach, dubbed Regularized Routing Optimization (RRO). The RRO algorithm offers both distributed and centralized implementations with low complexity, making it suitable for integration into 5G and beyond tech-nologies, where no significant changes to the existing protocols are needed. It increases throughput while ensuring latency remains sufficiently low through regularized optimization. We analyze the computational complexity of RRO and prove that it converges with a level of complexity comparable to OSPF. Extensive simulation results across diverse network topologies demonstrate that RRO significantly outperforms existing methods.

In the rapidly evolving landscape of wireless networks, achieving enhanced throughput with low latency for data transmission is crucial for future communication systems. While low complexity OSPF-type solutions have shown effectiveness in lightly-loaded networks, they often falter in the face of increasing congestion. Recent approaches have suggested utilizing backpressure and deep learning techniques for route optimization. However, these approaches face challenges due to their high implementation and computational complexity, surpassing the capabilities of networks with limited hardware devices. A key challenge is developing algorithms that improve throughput and reduce latency while keeping complexity levels compatible with OSPF. In this collaborative research between Ben-Gurion University and Ceragon Networks Ltd., we address this challenge by developing a novel approach, dubbed Regularized Routing Optimization (RRO). The RRO algorithm offers both distributed and centralized implementations with low complexity, making it suitable for integration into 5G and beyond technologies, where no significant changes to the existing protocols are needed. It increases throughput while ensuring latency remains sufficiently low through regularized optimization. We analyze the computational complexity of RRO and prove that it converges with a level of complexity comparable to OSPF. Extensive simulation results across diverse network topologies demonstrate that RRO significantly outperforms existing methods.

We consider the distributed message-passing model and the Local Computational Algorithms (LCA) model. In both models a network is represented by an n -vertex graph G = ( V , E ) . We focus on labeling problems, such as vertex-coloring, edge-coloring, maximal independent set (MIS) and maximal matching. In the distributed model the vertices of v perform computations in parallel in order to compute their own solution for solving the problem for G . In contrast, in the LCA model probes are performed on certain vertices in order to compute their labels in a solution to a given problem. In this work we study the possibility of estimating a solution produced by an algorithm, much before the algorithm terminates. This estimation not only allows for size approximation of a solution, but also for early detection of failure in randomized algorithms. We do this such that a correcting procedure can be executed. To this end, we propose a sampling technique, in which the labels in the sampling are distributed proportionally to the distribution in the algorithm's output. However, the sampling running time is significantly smaller than that of the algorithm in hand. We achieve the following results, in terms of the maximum degree Δ and the arboricity a of the input graph. The running time of our procedures is O ( log ⁡ a + log ⁡ log ⁡ n ) , for sampling vertex-coloring, edge-coloring, maximal matching and MIS. This significantly improves upon previous sampling techniques, which incur additional dependency on the maximum degree Δ that can be much higher than the arboricity, as well as more significant dependency on n . Not only that, we also show that our technique extends naturally for the power graph G r for any constant integer r > 1 for the problems of MIS and coloring. Our techniques for sampling in the distributed model provide a powerful and general tool for estimation in the LCA model. In this setting the goal is estimating the size of a solution to a given problem, by making as few vertex probes as possible. For the above-mentioned problems, we achieve estimations with probe complexity d O ( log ⁡ a + log ⁡ log ⁡ n ) , where d = m i n ( Δ , a ⋅ p o l y ( log ⁡ ( n ) ) . Our results extend as well to power graphs for the coloring and MIS problems.

In this paper we provide a deterministic scheme for solving any decidable problem in the distributed sleeping model. The sleeping model [Valerie King et al., 2011; Soumyottam Chatterjee et al., 2020] is a generalization of the standard message-passing model, with an additional capability of network nodes to enter a sleeping state occasionally. As long as a vertex is in the awake state, it is similar to the standard message-passing setting. However, when a vertex is asleep it cannot receive or send messages in the network nor can it perform internal computations. On the other hand, sleeping rounds do not count towards awake complexity. Awake complexity is the main complexity measurement in this setting, which is the number of awake rounds a vertex spends during an execution. In this paper we devise algorithms with worst-case guarantees on the awake complexity. We devise a deterministic scheme with awake complexity of O(log n) for solving any decidable problem in this model by constructing a structure we call Distributed Layered Tree. This structure turns out to be very powerful in the sleeping model, since it allows one to collect the entire graph information within a constant number of awake rounds. Moreover, we prove that our general technique cannot be improved in this model, by showing that the construction of distributed layered trees itself requires Ω(log n) awake rounds. This is obtained by a reduction from message-complexity lower bounds, which is of independent interest. Furthermore, our scheme also works in the CONGEST setting where we are limited to messages of size at most O(log n) bits. This result is shown for a certain class of problems, which contains problems of great interest in the research of the distributed setting. Examples for problems we can solve under this limitation are leader election, computing exact number of edges and average degree. Another result we obtain in this work is a deterministic scheme for solving any problem from a class of problems, denoted O-LOCAL, in O(log Δ + log^*n) awake rounds. This class contains various well-studied problems, such as MIS and (Δ+1)-vertex-coloring. Our main structure in this case is a tree as well, but is sharply different from a distributed layered tree. In particular, it is constructed in the local memory of each processor, rather than distributively. Nevertheless, it provides an efficient synchronization scheme for problems of the O-LOCAL class.

We consider the distributed synchronous message passing model, also known as theLOCALmodel. In this model the input graphGrepresents a network, where each vertex in the graph is a processor and each edge is a communication line between two processors. Symmetry-breaking problems are among the most studied problems in this model [4], [7], [9]-[11], [13], [17], [18], [23], [24], [26]. In this paper we devise a general method for solving symmetry breaking problems in graphs with boundeddiversity. Roughly speaking, the diversity of a graph is the maximum number of maximal cliques a vertex belongs to. This general method uses a new approach which utilizes a structure calleda connector. We build a series of such connectors, each of which simplifies the previous one by decreasing maximum clique size. Eventually, cliques becomes sufficiently small and have some additional properties that allow us to bound the maximum degree of the connectors. Then it becomes possible to employ efficient symmetry-breaking algorithms for bounded-degree graphs and extend the results to all the connectors in the series in backward order, until we reach a solution for the original graph. We use the ideas of this general method to achieve the following results. First, we devise an improved algorithm for maximal matching with running time ofO(log(S)(D(G) + log*n)), whereD(G) is the diversity ofGandS(G) is the maximum clique size. The best currently-known deterministic result for general graphs isO(log2Δlogn) [13]. This result is also the best currently-known for graphs with bounded diversity, hence our result constitutes an improvement for graphs withD(G) =o(log Δ logn). Another algorithm of ours for the same problem has a running time ofO(D(G)2+ log*n). For graphs withD(G) =O(1) this shows a separation of complexities between the maximal matching problem and the maximal independent set problem. Indeed, in such graphs our algorithm computes a maximal matching withinO(log*n) time, while computing a maximal independent set requires Ω(√(logn/ log logn)) time. This is the first result for any family of graphs that shows that maximal matching is provably easier than maximal independent set in the distributed setting. Moreover, using the same methods, we devise improved algorithms for ruling sets in graphs with bounded diversity. We also obtain an improved result for the wider family of graphs with bounded neighborhood independence ℓ. Specifically, we compute a maximal matching withinO(ℓ log Δ + log*n) time in such graphs.

In the distributed message-passing setting a communication network is represented by a graph whose vertices represent processors that perform local computations and communicate over the edges of the graph. In the distributed edge-coloring problem the processors are required to assign colors to edges, such that all edges incident on the same vertex are assigned distinct colors. The previously-known deterministic algorithms for edge-coloring employed at least (2Δ - 1) colors, even though any graph admits an edge-coloring with Δ + 1 colors [36]. Moreover, the previously-known deterministic algorithms that employed at most O(Δ) colors required superlogarithmic time [3,6,7,17]. In the current paper we devise deterministic edge-coloring algorithms that employ only Δ + o(Δ) colors, for a very wide family of graphs. Specifically, as long as the arboricity a of the graph is a = O(Δ1 - ε), for a constant ε > 0, our algorithm computes such a coloring within polylogarithmic deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for general graphs for a very wide range of parameters. Specifically, for any value κ in the range [4Δ, 2o(log Δ) ⋅ Δ], our κ-edge-coloring algorithm has smaller running time than the best previously-known κ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to vertex-coloring of line graphs. Our method is applicable to vertex-coloring of the family of graphs with bounded diversity that contains line graphs, line graphs of hypergraphs, and many other graphs. We significantly improve upon previous vertex-coloring of such graphs, and as an implication also obtain the improved edge-coloring algorithms for general graphs.