Abstract Energy efficiency is one of the most critical aspects of modern computing paradigms due to minimizing carbon footprint and lowering operational costs. To achieve efficiency, the typical approach is to address the source of energy consumption and apply the appropriate strategies for energy savings. In this paper, based on an offloading framework for edge and cloud computing, we propose a comprehensive methodology that leverages predictive analysis and convex optimization techniques to achieve efficiency in power utilization. This methodology aimed to reduce the power consumption of edge/cloud computing clusters while maintaining an acceptable quality of service. The core idea was to enhance the historical data in the first place by using the prediction. This predictive historical data revealed the trend of computational resource allocation. Subsequently, the convex optimization technique coupled with the Deep Q-Network model was employed to formulate and schedule the distribution of the offloaded tasks. By engaging this combination, the offloading framework could produce a near-optimal and adaptive energy decision, which helps achieve energy efficiency. The experimental results showed that the proposed methodology could obtain significant energy savings while maintaining a suitable level of performance compared to other state-of-the-art approaches.

https://drops.dagstuhl.de/storage/00lipics/lipics-vol275-approx-random2023/LIPIcs.APPROX-RANDOM.2023.66/LIPIcs.APPROX-RANDOM.2023.66.pdf

We initiate a systematic study of tolerant testers of image properties or, equivalently, algorithms that approximate the distance from a given image to the desired property. Image processing is a particularly compelling area of applications for sublinear-time algorithms and, specifically, property testing. However, for testing algorithms to reach their full potential in image processing, they have to be tolerant, which allows them to be resilient to noise. We design efficient approximation algorithms for the following fundamental questions: What fraction of pixels have to be changed in an image so it becomes a half-plane? A representation of a convex object? A representation of a connected object? More precisely, our algorithms approximate the distance to three basic properties (being a half-plane, convexity, and connectedness) within a small additive error ε, after reading poly (1/ε) pixels, independent of the image size. We also design an efficient agnostic proper PAC learner of convex sets (continuous and discrete) in two dimensions under the uniform distribution. Our algorithms require very simple access to the input: uniform random samples for the half-plane property and convexity, and samples from uniformly random blocks for connectedness. However, the analysis of the algorithms, especially for convexity, requires many geometric and combinatorial insights. For example, in the analysis of the algorithm for convexity, we define a set of reference polygons P ε such that (1) every convex image has a nearby polygon in P ε and (2) one can use dynamic programming to quickly compute the smallest empirical distance to a polygon in P ε .

In this paper we present several results on the expected complexity of a convex hull of $n$ points chosen uniformly and independently from a convex shape. (i) We show that the expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from a disk is $O(n^{1/3})$, and $O(k \log{n})$ for the case a convex polygon with $k$ sides. Those results are well known (see \cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that the elementary proof given here are simpler and more intuitive. (ii) Let $\D$ be a set of directions in the plane, we define a generalized notion of convexity induced by $\D$, which extends both rectilinear convexity and standard convexity. We prove that the expected complexity of the $\D$-convex hull of a set of $n$ points, chosen uniformly and independently from a disk, is $O(n^{1/3} + \sqrt{nα(\D)})$, where $α(\D)$ is the largest angle between two consecutive vectors in $\D$. This result extends the known bounds for the cases of rectilinear and standard convexity. (iii) Let $\B$ be an axis parallel hypercube in $\Re^d$. We prove that the expected number of points on the boundary of the quadrant hull of a set $S$ of $n$ points, chosen uniformly and independently from $\B$ is $O(\log^{d-1}n)$. Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in $S$, and is also larger than the number of points of $S$ that are vertices of the convex hull of $S$. Those bounds are known \cite{bkst-anmsv-78}, but we believe the new proof is simpler.

We investigate testing of properties of 2-dimensional figures that consist of a black object on a white background. Given a parameter epsilon in (0,1/2), a tester for a specified property has to accept with probability at least 2/3 if the input figure satisfies the property and reject with probability at least 2/3 if it does not. In general, property testers can query the color of any point in the input figure. We study the power of testers that get access only to uniform samples from the input figure. We show that for the property of being a half-plane, the uniform testers are as powerful as general testers: they require only O(1/epsilon) samples. In contrast, we prove that convexity can be tested with O(1/epsilon) queries by testers that can make queries of their choice while uniform testers for this property require Omega(1/epsilon^{5/4}) samples. Previously, the fastest known tester for convexity needed Theta(1/epsilon^{4/3}) queries.