A power-down system has an on-state, an off-state, and a finite or infinite number of intermediate states. In the off-state, the system uses no energy and in the on-state energy it is used fully. Intermediate states consume only some fraction of energy but switching back to the on-state comes at a cost. Previous work has mainly focused on asymptotic results for systems with a large number of states. In contrast, the authors study problems with a few states as well as systems with one continuous state. Such systems play a role in energy-efficiency for information technology but are especially important in the management of renewable energy. The authors analyze power-down problems in the framework of online competitive analysis as to obtain performance guarantees in the absence of reliable forecasting. In a discrete case, the authors give detailed results for the case of three and five states, which corresponds to a system with on-off states and three additional intermediate states “power save”, “suspend”, and “hibernate”. The authors use a novel balancing technique to obtain optimally competitive solutions. With this, the authors show that the overall best competitive ratio for three-state systems is and the authors obtain optimal ratios for various five state systems. For the continuous case, the authors develop various strategies, namely linear, optimal-following, progressive and exponential. The authors show that the best competitive strategies are those that follow the offline schedule in an accelerated manner. Strategy “progressive” consistently produces competitive ratios significantly better than 2.
1 March 2022 in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical; however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear- and constant-time algorithms are required. The academic research project, “Foundations of Innovative Algorithms for Big Data,” which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a “Sublinear Computation Paradigm.” Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present Sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.
1 September 2019 in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
We present constant-time testing algorithms for generalized shogi (Japanese chess), chess, and xiangqi (Chinese chess). These problems are known or believed to be EXPTIME-complete. A testing algorithm (or a tester) for a property accepts an input if it has the property, and rejects it with high probability if it is far from having the property (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if a tester exists. Given any position on a ⌊√n⌋×⌊√n⌋ board with O(n) pieces, the generalized shogi, chess, and xiangqi problem are problems determining the property that “the player who moves first has a winning strategy.” We propose that this property is testable for shogi, chess, and xiangqi. The shogi tester and xiangqi tester have a one-sided-error, but surprisingly, the chess tester has no-error. Over the last decade, many problems have been revealed to be testable, but most of such problems belong to NP. This is the first result on the constant-time testability of EXPTIME-complete problems.