13865930
Proxy-Assisted Scheduling for Energy-Efficient Multimedia Streaming over Wireless LAN
Energy is a critical resource for battery-driven mobile and wireless devices. The power-saving mode (PSM) provided by the 802.11 standard is not adequate for mobile clients running streaming media applications. We propose new power-aware scheduling strategies that enhance existing traffic shaping schemes for the purpose of minimizing the communication energy consumption of mobile clients. Scheduling decisions are made by the local proxy and executed at the access point. We consider two cases. In the first case, the proxy is unaware of the power characteristics of the clients. We present an optimal scheduling scheme that minimizes the time that mobile clients stay in high-power modes. This scheme achieves significant energy savings compared to using traffic shaping alone. In the second case, the power profiles and the residual battery capacities of the clients are taken into account in generating the schedule. Unlike most existing work, we believe these factors should be considered in the performance metric. We propose a dynamic programming approach that computes the optimal transmission schedule based on the new metric. We also present an efficient heuristic which exhibits near-optimal performance in the simulation experiments.
1083190
Streaming media caching algorithms for transcoding proxies
Streaming media is expected to become one of the most popular types of Web content in the future. Due to increasing variety of client devices and the range of access speeds to the Internet, multimedia contents may be required to be transcoded to match the client's capability. With transcoding, both the network and the proxy CPU are potential bottlenecks for streaming media delivery. This paper discusses and compares various caching algorithms designed for transcoding proxies. In particular we propose a new adaptive algorithm that dynamically selects an appropriate metric for adjusting the management policy. Experimental results show that the proposed algorithm significantly outperforms those that cache only untranscoded or only transcoded objects. Moreover motivated by the characteristics of many video compression algorithms, we investigate partitioning a video object into sections based on frame type and handling them individually for proxy caching. It is found that partitioning improves performance when CPU power rather than network bandwidth is the limiting resource, particularly when the reference pattern is not highly skewed.
1746401
On the Effective Enumerability of NP Problems
In the field of computational optimization, it is often the case that we are given an instance of an NP problem and asked to enumerate the first few best solutions to the instance. Motivated by this, we propose in this paper a new framework to measure the effective enumerability of NP optimization problems. More specifically, given an instance of an NP problem, we consider the parameterized problem of enumerating a given number of best solutions to the instance, and study its average complexity in terms of the number of solutions. Our framework is different from the previously-proposed ones. For example, although it is known that counting the number of k-paths in a graph is #W[1]-complete, we present a fixed-parameter enumeration algorithm for the problem. We show that most algorithmic techniques for fixed-parameter tractable problems, such as search trees, color coding, and bounded treewidth, can be used for parameterized enumerations. In addition, we design elegant and new enumeration techniques and show how to generate small-size structures and enumerate solutions efficiently.
41496800
Intra-Organizational Logistics Management Through Multi-Agent Systems
Compared to inter-organizational logistics management, the goal of intra-organizational logistics management is to maximize the profits of the whole company sometimes at the cost of its individual units' profits. While many agent-based models have been proposed for logistics management, most of these models use an auction approach. Thus, they are not suitable for intra-organizational logistics management. In this paper, we first formulate logistics management as a distributed resource allocation problem. Then, we present our ongoing work on developing a multi-agent model for intra-organizational logistics management and using Lagrangian relaxation to decompose the problem into a set of subproblems. Our initial experimental results are very promising. We provide a detailed analysis of our results.
41201857
A Note on the Number of Perfect Matchings of Bipartite Graphs
Abstract Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s + 2, s ϵ {1, 2, …}, an elegant formula, i.e. det A = (−1)nK2, had been rigorously proved by Cvetkovic et al. (1982). For general bipartite graphs, this note contains a necessary and sufficient condition for the above relation to hold. A fast algorithm to check if a plane bipartite graph has such a relation is given.
45999842
The number of spanning trees in odd valent circulant graphs
In this paper, we consider the number of spanning trees in circulant graphs. For any class of odd valent circulant graphs C"2"n(a"1,a"2,...,a"k"-"1,n), where a"1,a"2,...,a"k"-"1 are fixed jumps and n varies, some formulas, asymptotic behaviors and linear recurrence relations for the number of its spanning trees are obtained, and some known results on the ones in even valent circulant graphs C"n(a"1,a"2,...,a"k) are improved.
5788058
Heredity of the index of convergence of the line digraph
Let D be a digraph, and let Ln(D) and k(D) denote the nth iterated line digraph of D and the index of convergence of D, respectively. We prove that if D contains neither sources nor sinks, then: (1) k(Ln(D))=k(D)=0 if every connected component of D is a directed cycle. (2) k(Ln(D))=k(D)+n if there exists at least one connected component of D that is not a directed cycle. Finally, we prove that if D has no sources or no sinks then k(D) ≤ k(L(D)) ≤ k(D)+1.