We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA(0) ...
详细信息
We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA(0) and hence is computably true.
This paper investigates the Minimizing-Interference-for-Multiple-Paths (MIMP) problem for routing with minimum interference in wireless sensor networks, which is defined as: Given k routing requests {s(1), t(1)},..., ...
详细信息
This paper investigates the Minimizing-Interference-for-Multiple-Paths (MIMP) problem for routing with minimum interference in wireless sensor networks, which is defined as: Given k routing requests {s(1), t(1)},..., {s(k), t(k)}, find k paths connecting these routing requests with minimum (wireless) interference. A key point to solve this problem is how to quantify interference level among multiple routing paths. However, all the existing metrics cannot measure interference precisely under some certain circumstances, e.g., some of the routing paths have common nodes or links. This paper proposes a metric that can measure interference precisely among any set of paths, even though these paths have some nodes or links in common. For this proposed metric, the MIMP problem is NP-hard even for k = 2. A heuristic Distributed on-line algorithm for Minimizing Interference (DOAMI) is given to solve the MIMP problem. DOAMI has good communication and time complexity in theory, whose efficiency is also verified by simulation results. (C) 2016 Published by Elsevier B.V.
An on-line scheduling problem on m uniform parallel-batch machines to minimize the makespan is considered in this paper. Each machine can process infinite jobs as a batch at a time. Jobs arrive over time and have equa...
详细信息
An on-line scheduling problem on m uniform parallel-batch machines to minimize the makespan is considered in this paper. Each machine can process infinite jobs as a batch at a time. Jobs arrive over time and have equal lengths denoted by 1. Compared to parallel machines, uniform machines are more difficult to deal with because they have different processing speeds. There are two types of machines in our model. The lower bound on the competitive ratio is characterized by some complicated algebraic equations. And a best possible on-line algorithm matching the lower bound is constructed and proved in this paper. (C) 2018 Elsevier B.V. All rights reserved.
There are many obstacles preventing new learners of the Guzheng from getting faster improvements. For example, the need to flip the music sheet with one hand interrupts the consistency of the performance. To overcome ...
详细信息
ISBN:
(纸本)9781538668122;9781538668115
There are many obstacles preventing new learners of the Guzheng from getting faster improvements. For example, the need to flip the music sheet with one hand interrupts the consistency of the performance. To overcome these difficulties, an on-line algorithm for music-to-score alignment is proposed in this paper, whose function is to detect and trace the progress of the music signal recorded by a microphone. The use of Dynamic Time Warping (DTW) technique helps to align the standard music and the recording. Therefore, it is possible to show the progress on the screen in the real time and flip the page automatically when it is required. Furthermore, the errors of the player's performance can also be detected with further improvements of the algorithm.
Nowadays, wireless LAN has become the most widely deployed technology in mobile devices for providing Internet access. Operators and service providers remarkably increase the density of wireless access points in order...
详细信息
Nowadays, wireless LAN has become the most widely deployed technology in mobile devices for providing Internet access. Operators and service providers remarkably increase the density of wireless access points in order to provide their subscribers with better connectivity and user experience. As a result, WLAN users usually find themselves covered by multiple access points and have to decide which one to associate with. In traditional implementations, most wireless stations would select the access point with the strongest signal, regardless of traffic load on that access point, which might result in heavy congestion and unfair load. In this paper, we propose a novel on-line association algorithm to deal with any sequence of STAs during a long-term time such as one day. the performance of our algorithm is evaluated through simulation and experiments. Simulation results show that our algorithm improves the overall WLAN throughput by up to 37%, compared with the conventional RSSI-based approach. Our algorithm also performs better than SSF (Strongest Signal First) and LAB (Largest Available Bandwidth) in the experiments.
This paper considers an on-line scheduling and routing problem concerning the automated storage and retrieval system from tobacco industry. In this problem, stacker cranes run on one common rail between two racks. Mul...
详细信息
This paper considers an on-line scheduling and routing problem concerning the automated storage and retrieval system from tobacco industry. In this problem, stacker cranes run on one common rail between two racks. Multiple input/output-points are located at the bottom of the racks. The stacker cranes transport bins between the input/output-points and cells on the racks to complete requests generated over time. Each request should be accomplished within its response time. The objective is to minimize the time by which all the generated requests are completed. Under a given physical layout, the authors study the complexity of the problem and design on-line algorithms for both one-stacker-crane model and two-stacker-crane model. The algorithms axe validated by instances and numerical simulations.
The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as...
详细信息
The existence of an on-line competitive algorithm for coloring bipartite graphs is a tantalizing open problem. So far there are only partial positive results for bipartite graphs with certain small forbidden graphs as induced subgraphs. We propose an on-line competitive coloring algorithm for -free bipartite graphs.
In IaaS cloud services, QoS of network applications (NW-Apps) may degrade due to location factors such as significant distance between a server-side application (server) of a NW-App at a data center and a client-side ...
详细信息
ISBN:
(纸本)9781479963904
In IaaS cloud services, QoS of network applications (NW-Apps) may degrade due to location factors such as significant distance between a server-side application (server) of a NW-App at a data center and a client-side application (client) of the NW-App at a client terminal. In order to shorten the distance and to improve the QoS, server migration services (SMSes) have been proposed. In SMSes, servers may migrate between different computers (called work places, WPs) on a network to prevent QoS degradation caused by the changes of client locations. Although server migrations can improve QoS of NW-Apps, they also generate a huge amount of traffic (server migration traffic) in the network. This paper focuses on a server location decision problem where the location of a server is decided in an on-line manner so that QoS of a NW-App is improved under the constraint that the server migration traffic has to be suppressed below an acceptable level. For the problem, we propose a practical on-line algorithm. The key idea behind the proposed algorithm is that the location of the server is decided with consideration of the QoS degradation in the future. The algorithm defines the averagely good location for the server where the QoS is expected to be relatively good for various client locations. Then, it keeps the range of the server's migration within the returnable range where the server can soon come back to the averagely good location. As a result, the QoS can be always kept as good as the one under the averagely good location. Simulation results show that the proposed algorithm improves QoS of the NW-App by up to 30% compared to a greedy algorithm.
In this paper, we consider the on-line single machine scheduling of unit time jobs with rejection. All jobs arrive on-line over a list (one by one). For each arriving job, the on-line algorithm must decide immediately...
详细信息
In this paper, we consider the on-line single machine scheduling of unit time jobs with rejection. All jobs arrive on-line over a list (one by one). For each arriving job, the on-line algorithm must decide immediately to accept or reject it. The objective is to minimize the maximum quadratic completion time of accepted jobs plus the total rejection cost of rejected jobs. For this problem, we show that 1.7299 is a lower bound on the competitive ratio and present a simple greedy algorithm with the competitive ratio 2. Furthermore, we also provide a modified greedy algorithm with a better competitive ratio 1 + root 3/2 approximate to 1.86602.
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemeredi proved that any on-line algorithm could be forced...
详细信息
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemeredi proved that any on-line algorithm could be forced to use (2(w+1)) chains to partition a poset of width w. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In a survey paper by Bosek et al., it is shown that Szemeredi's argument could be improved to obtain a lower bound almost twice as good. Variants of the problem were considered where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size d. In this paper, we prove two results. First, we prove that any on-line algorithm can be forced to use (2 - o(1))(2(w+1)) chains to partition a 2-dimensional poset of width w. Second, we prove that any on-line algorithm can be forced to use (2 - 1/d-1 - o(1))(2(w+1)) chains to partition a poset of width w presented via a realizer of size d.
暂无评论