检索结果-内蒙古大学图书馆

Soundprism: An online System for Score-Informed Source Separation of Music Audio

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2011年第6期5卷 1205-1215页

作者： Duan, Zhiyao Pardo, Bryan Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

Soundprism, as proposed in this paper, is a computer system that separates single-channel polyphonic music audio played by harmonic sources into source signals in an online fashion. It uses a musical score to guide the separation process. To the best of our knowledge, this is the first online system that addresses score-informed music source separation that can be made into a real-time system. The proposed system consists of two parts: 1) a score follower that associates a score position to each time frame of the audio performance;2) a source separator which reconstructs the source signals for each time frame, informed by the score. The score follower uses a hidden Markov approach, where each audio frame is associated with a 2-D state vector (score position and tempo). The observation model is defined as the likelihood of observing the frame given the pitches at the score position. The score position and tempo are inferred using particle filtering. In building the source separator, we first refine the score-informed pitches of the current audio frame by maximizing the multi-pitch observation likelihood. Then, the harmonics of each source's fundamental frequency are extracted to reconstruct the source signal. Overlapping harmonics between sources are identified and their energy is distributed in inverse proportion to the square of their respective harmonic number. Experiments on both synthetic and human-performed music show both the score follower and the source separator perform well. Results also show that the proposed score follower works well for highly polyphonic music with some degree of tempo variations.

关键词： Multi-pitch estimation online algorithm score following source separation

来源：评论

学校读者我要写书评

暂无评论

Peak-Aware online Economic Dispatching for Microgrids

引用

IEEE TRANSACTIONS ON SMART GRID 2018年第1期9卷 323-335页

作者： Zhang, Ying Hajiesmaili, Mohammad H. Cai, Sinan Chen, Minghua Zhu, Qi Chinese Univ Hong Kong Dept Informat Engn Hong Kong Hong Kong Peoples R China Xi An Jiao Tong Univ Sch Elect Engn Xian 710049 Peoples R China Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids;however, it is drastically different from that for conventional central grids due to two unique challenges. First, the demand and renewable generation uncertainty emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. We prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2-beta and e/(e - 1 + beta) in the fast responding generator scenario, where beta. [0, 1] is the ratio between the minimum grid spot price and the local-generation price. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 17.5% and 9.24% cost reduction as compared with the case without local generation units and the case using peak-oblivious algorithms, respectively.

关键词： Microgrids online algorithm peak-aware scheduling economic dispatching

来源：评论

学校读者我要写书评

暂无评论

online unit covering in Euclidean space

引用

THEORETICAL COMPUTER SCIENCE 2020年 809卷 218-230页

作者： Dumitrescu, Adrian Ghosh, Anirban Toth, Csaba D. Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA Univ North Florida Sch Comp Jacksonville FL 32224 USA Calif State Univ Northridge Dept Math Los Angeles CA USA Tufts Univ Dept Comp Sci Medford MA 02155 USA

We revisit the online UNIT COVERING problem in higher dimensions: Given a set of n points in R-d, that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in R-d using the Euclidean distance. (I) We give an online deterministic algorithm with competitive ratio O(1.321(d)), thereby improving on the previous record, O(2(d)d logd), due to Charikar et al. (2004), by an exponential factor. In particular, the competitive ratios are 5 in the plane and 12 in 3-space (the previous ratios were 7 and 21, respectively). For d = 3, the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm for UNIT COVERING in R-d under the L-2 norm is at least d + 1 for every d >= 1. This greatly improves upon the previous best lower bound, Omega(logd/ log loglogd), due to Charikar et al. (2004). (III) We generalize the above result to UNIT COVERING in R-d under the L-C norm, where C is a centrally symmetric convex body, via the illumination number. (IV) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online UNIT COVERING in R-2 and R-3, respectively;the previous best lower bounds were 3 for both cases. (V) When the input points are from the square or hexagonal lattice in R-2, we give deterministic online algorithms for UNIT COVERING with an optimal competitive ratio of 3. For the cubic lattice in R-3, we give a deterministic online algorithm with a competitive ratio of 5. (C) 2019 Elsevier B.V. All rights reserved.

关键词： online algorithm Unit covering Unit clustering Competitive ratio Illumination number Newton number

来源：评论

学校读者我要写书评

暂无评论

online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2023年第11期74卷 2432-2454页

作者： Wei, Qi Wu, Yong Cheng, T. C. E. Sun, Fengxin Jiang, Yiwei Ningbo Univ Finance & Econ Ningbo Peoples R China Hong Kong Polytech Univ Kowloon Hong Kong Peoples R China Ningbo Univ Technol Ningbo Peoples R China Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Hangzhou Peoples R China Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Sch Management & E Business Hangzhou 310018 Peoples R China

We consider online hierarchical scheduling on m identical machines in shared manufacturing to minimize the total completion time. Each job has a unit-size processing time. The jobs arrive one by one and must be assigned to one of the m machines before the next job arrives. The jobs with a lower hierarchy can only be processed on the first k machines, 1 <= k <= m-1, and the jobs with a higher hierarchy can be processed on any one of the m machines. We first show that the lower bound of the problem is at least 1+min{1/m-k+1,max{2/k inverted right perpendiculexpressionr s right ceiling +3k+2m+4/ inverted right perpendiculexpressionr s right ceiling ,2/k left floor s right floor +3k+2m+4/ left floor s right floor }}, where s=root 2m+4/k. Proposing a greedy algorithm, we show that its tight competitive ratio is 1+2(m-k)k/m(root(4m-3k)k root+k)by analyzing a set of instances that must contain a worst-case instance, which is different from the general method of calculating the competitive ratio. In addition, for the case where k = 1, we present an improved online algorithm with a tight competitive ratio of 1+max{2/ inverted right perpendiculexpressionr root 2m+4 root right ceiling +2m+4/ inverted right perpendiculexpressionr root 2m+4 root right ceiling +3,2/ left floor root 2m+4 right floor +2m+4/ left floor root 2m+4 root right floor +3}, which is optimal for 2 <= m <= 5. Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.

关键词： Share manufacturing hierarchical scheduling online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for online single machine scheduling with deteriorating jobs

引用

THEORETICAL COMPUTER SCIENCE 2012年 445卷 75-81页

作者： Liu, Ming Zheng, Feifeng Wang, Shijin Huo, Jiazhen Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Xi An Jiao Tong Univ Sch Management Xian 710049 Shaanxi Peoples R China

In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job's deterioration effect. Such effect is unexplored in the context of online environment. In this paper we study online single machine scheduling for deteriorating jobs, where jobs arrive over time and become known to any online algorithm on their arrivals. The processing time of each job is a linearly increasing function of its start time. We mainly investigate three online models that minimize makespan, total completion time and maximum delivery time, respectively. For each model we present an optimal online algorithm in competitiveness. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithm Deteriorating job Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Obtaining online approximation algorithms for facility dispersion from offline algorithms

引用

NETWORKS 2006年第4期47卷 206-217页

作者： Rosenkrantz, Daniel J. Tayi, Giri K. Ravi, S. S. SUNY Albany Dept Comp Sci Albany NY 12222 USA SUNY Albany Sch Business Dept Management Sci & Informat Syst Albany NY 12222 USA

Facility dispersion problems arise in the context of placing obnoxious facilities and retail outlets. In the off line version of such a problem, the input consists of a complete graph on n nodes, a nonnegative weight (distance) for each edge, and the number k <= n of facilities to be placed. The goal is to choose a facility placement consisting of k nodes so as to maximize a given measure of the distances among the facilities. Here, we consider an online version of the problem where the value of k is not known apriori;instead, requests for facilities arrive one at a time. It is also required that previously placed facilities cannot be moved or eliminated. Our main result is that for any objective that satisfies two properties, namely monotonicity and graceful degradation, any off line approximation algorithm with a performance guarantee p can be used to develop an algorithm with competitive ratio c rho for the online version, where c is a constant independent of the problem instance. Objectives for which our result applies include the average edge weight and average weight of a star subgraph. The result holds even when the edge weights do not satisfy the triangle inequality. We also identify dispersion objectives for which the offline and online versions have different behaviors when only one of the above two properties Is satisfied. (C) 2006 Wiley Periodicals, Inc.

关键词： facility dispersion offline algorithm online algorithm approximation ratio competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2014年第3期74卷 2180-2192页

作者： Sun, Hongyang Hsu, Wen-Jing Cao, Yangjie Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore Zhengzhou Univ Sch Software Engn Zhengzhou Peoples R China

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at anytime. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs' execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Adaptive scheduling Parallel jobs Set response time Multiprocessors online algorithm Competitive analysis Hierarchical scheduling Fairness Efficiency

来源：评论

学校读者我要写书评

暂无评论

online estimation of noise parameters for Kalman filter

引用

STRUCTURAL ENGINEERING AND MECHANICS 2013年第3期47卷 361-381页

作者： Yuen, Ka-Veng Liang, Peng-Fei Kuok, Sin-Chi Univ Macau Fac Sci & Technol Dept Civil & Environm Engn Taipa Peoples R China

A Bayesian probabilistic method is proposed for online estimation of the process noise and measurement noise parameters for Kalman filter. Kalman filter is a well-known recursive algorithm for state estimation of dynamical systems. In this algorithm, it is required to prescribe the covariance matrices of the process noise and measurement noise. However, inappropriate choice of these covariance matrices substantially deteriorates the performance of the Kalman filter. In this paper, a probabilistic method is proposed for online estimation of the noise parameters which govern the noise covariance matrices. The proposed Bayesian method not only estimates the optimal noise parameters but also quantifies the associated estimation uncertainty in an online manner. By utilizing the estimated noise parameters, reliable state estimation can be accomplished. Moreover, the proposed method does not assume any stationarity condition of the process noise and/or measurement noise. By removing the stationarity constraint, the proposed method enhances the applicability of the state estimation algorithm for nonstationary circumstances generally encountered in practice. To illustrate the efficacy and efficiency of the proposed method, examples using a fifty-story building with different stationarity scenarios of the process noise and measurement noise are presented.

关键词： Bayesian probabilistic approach Kalman filter online algorithm process noise measurement noise structural health monitoring

来源：评论

学校读者我要写书评

暂无评论

online Throughput Maximization for Energy Harvesting Communication Systems with Battery Overflow

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2017年第1期16卷 185-197页

作者： Wu, Weiwei Wang, Jianping Wang, Xiumin Shan, Feng Luo, Junzhou Southeast Univ Sch Comp Sci & Engn Nanjing Jiangsu Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China HeFei Univ Technol Sch Comp & Engn Hefei Anhui Peoples R China

Energy harvesting communication system enables energy to be dynamically harvested from natural resources and stored in capacitated batteries to be used for future data transmission. In such a system, the amount of future energy to harvest is uncertain and the battery capacity is limited. As a consequence, battery overflow and energy dropping may happen, causing energy underutilization. To maximize the data throughput by using the energy efficiently, a rate-adaptive transmission schedule must address the trade-off between a high- rate transmission which avoids energy overflow and a low-rate transmission which avoids energy shortage. In this paper, we study an online throughput maximization problem without knowing future information. To the best of our knowledge, this is the first work studying the fully-online transmission rate scheduling problem for battery-capacitated energy harvesting communication systems. We consider the problem under two models of the communication channel, a static channel model that assumes the channel status is stable, and a fading channel model that assumes the channel status varies. For the former, we develop an online algorithm that approximates the offline optimal solution within a constant factor for all possible inputs. For the latter, that the channel gains vary in range [h(min), h(max)], we propose an online algorithm with a proven Theta(log(h(max)/h(min)))-competitive ratio. Our simulation results further validate the efficiency of the proposed online algorithms.

关键词： Energy harvesting battery capacity energy overflow energy-efficient rate scheduling throughput maximization online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Randomized online File Allocation on Uniform Cactus Graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2009年第12期E92D卷 2416-2421页

作者： Kawamura, Yasuyuki Matsubayashi, Akira Kanazawa Univ Div Elect Engn & Comp Sci Kanazawa Ishikawa 9201192 Japan

We study the online file allocation problem on ring networks. In this paper, we present a 7-competitive randomized algorithm against an adaptive online adversary on uniform cactus graphs. The algorithm is deterministic if the file size is 1. Moreover, we obtain lower bounds of 4.25 and 3.833 fora deterministic algorithm and a randomized algorithm against an adaptive online adversary, respectively, on ring networks.

关键词： online algorithm file allocation data management cactus graph

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：