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

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Lieskovsky, Matej Charles Univ Prague Ovocny Trh 560-5 Prague 11636 1 Czech Republic

ISBN: (纸本)9783031555978;9783031555985

online BIN STRETCHING is a problem closely related to online BIN PACKING and various scheduling problems. There is extensive history of computer search being used to establish lower bounds for this problem by identifying difficult sets of inputs. We demonstrate a novel approach enabling the use of computer search for finding new algorithms and therefore upper bounds for this problem. This not only leads to improved results for online BIN STRETCHING, but also shows that computer search can be used to find new algorithms, even for problems that might not appear suitable for this approach.

关键词： Bin stretching Multiprocessor scheduling Bin packing online algorithms Computer search

来源：评论

学校读者我要写书评

暂无评论

New algorithms for online Unit Clustering

New Algorithms for Online Unit Clustering

引用

International Symposium on Telecommunications

作者： Mousavian, Zaynab Dezfoulian, Mir Hossein Bu Ali Sina Univ Dept Comp Engn Hamadan Iran

ISBN: (纸本)9781424427505

We study the online unit clustering problem introduced by Chan and Zarrabi-Zadeh at WAOA 2006. The problem in one dimension is as follows: Given a sequence of points on the real line, partition the points into clusters, each enclosable by a unit interval, with the objective of minimizing the number of clusters used. In this paper, we give a brief survey on the existing algorithms for this problem, and compare their efficiency in practice by implementing an deterministic and randomized algorithms proposed thus far for this problem in the literature. Meanwhile, we introduce two new deterministic algorithms that achieve better performance ratios on average in practice.

关键词： Unit clustering online algorithms Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online Ordinal Problems: Optimality of Comparison-based algorithms and their Cardinal Complexity 64

Online Ordinal Problems: Optimality of Comparison-based Algo...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Gravin, Nick Sun, Enze Tang, Zhihao Gavin Shanghai Univ Finance & Econ ITCS Key Lab Interdisciplinary Res Computat & Econ Shanghai Peoples R China Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9798350318944

We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of googol, as well as its multiple combinatorial extensions such as (J, K)-secretary, 2-sided game of googol, ordinal-competitive matroid secretary. A natural approach to these tasks is to use ordinal online algorithms that at each step only consider relative ranking among the arrived elements, without looking at the numerical values of the input. We formally study the question of how cardinal algorithms (that can use numerical values of the input) can improve upon ordinal algorithms. We give first a universal construction of the input distribution for any ordinal online problem, such that the advantage of any cardinal algorithm over the ordinal algorithms is at most 1 + epsilon for arbitrary small epsilon > 0. This implies that lower bounds from [Buchbinder, Jain, Singh, MOR 2014], [Nuti and Vondrak, SODA 2023] hold not only against any ordinal algorithm, but also against any online algorithm. Another immediate corollary is that cardinal algorithms are no better than ordinal algorithms in the matroid secretary problem with ordinal-competitive objective of [Soto, Turkieltaub, Verdugo, MOR 2021]. However, the value range of the input elements in our construction is huge: N = O(n(3).n!.n!/epsilon) up arrow up arrow (n-1) (tower of exponents) for an input sequence of length n. As a second result, we identify a class of natural ordinal problems and find cardinal algorithm with a matching advantage of 1+Omega(1/log((c)) N), where log((c)) N = log log ... log N with c iterative logs and c is an arbitrary constant c <= n-2. This suggests that for relatively small input numerical values N the cardinal algorithms may be significantly better than the ordinal algorithms on the ordinal tasks, which are typically assumed to be almost indistinguishable prior to our work. This observation leads to a natural c

关键词： online algorithms ordinal algorithms cardinal complexity secretary

来源：评论

学校读者我要写书评

暂无评论

Improved competitive algorithms for online scheduling with partial job values

引用

9th Annual International Computing and Combinatorics Conference (COCOON 2003)

作者： Chin, FYL Fung, SPY Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong Peoples R China

ISBN: (纸本)3540405348

This paper considers an online scheduling problem arising from Quality-of-Service (QoS) applications. We are required to schedule a set of jobs, each with release time, deadline, processing time and weight. The objective is to maximize the total value obtained for scheduling the jobs. Unlike the traditional model of this scheduling problem, in our model unfinished jobs also get partial values proportional to their amounts processed. We give a new non-timesharing algorithm GAP for this problem for bounded m, where m is the number of concurrent jobs or the number of weight classes. The competitive ratio is improved from 2 to 1.618 (golden ratio) which is optimal for m = 2, and when applied to cases with m > 2 it still gives a competitive ratio better than 2, e.g. 1.755 when m = 3. We also give a new study of the problem in the multiprocessor setting, giving an upper bound of 2 and a lower bound of 1.25 for the competitiveness. Finally, we consider resource augmentation and show that O(logalpha) speedup or extra processors is sufficient to achieve optimality, where alpha is the importance ratio. We also give a tradeoff result between competitiveness and the amount of extra resources.

关键词： online algorithms Partial job values Resource augmentation Scheduling

来源：评论

学校读者我要写书评

暂无评论

FAST online L₁-DICTIONARY LEARNING algorithms FOR NOVEL DOCUMENT DETECTION

FAST ONLINE L<sub>1</sub>-DICTIONARY LEARNING ALGORITHMS FOR...

引用

IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)

作者： Kasiviswanathan, Shiva Prasad Gen Elect Res San Ramon CA 94583 USA

ISBN: (纸本)9781479903566

online L-1-dictionary learning, introduced by Kasiviswanathan et al. [1], is the process of generating a sequence of (dictionary) matrices {A(t+1)}, one at a time, for t = 0, 1, .... After committing to A(t+1), a pair of matrices (Pt+1;Xt+1) is revealed and the online algorithm incurs a cost of parallel to Pt+1 - A(t+1)X(t+1)parallel to(1). The goal of the online algorithm is to ensure that the total cost up to each time is not much larger than the smallest total cost of any fixed A chosen with the benefit of hindsight. In this paper, we study three different algorithms for this problem based on the schemes of dual averaging, projected gradient, and alternating direction method of multipliers. We focus on the performance of these algorithms for the application of novel document detection, where online dictionary learning could be used to automatically identify emerging topics of discussion from a voluminous stream of text documents in a scalable manner. Our empirical results show the relative benefits of these three algorithms for this application.

关键词： Dictionary Learning Sparse Coding online algorithms Topic Detection

来源：评论

学校读者我要写书评

暂无评论

On time lookahead algorithms for the online data acknowledgement problem

引用

32nd International Symposium on Mathematical Foundations of Computer Science

作者： Imreh, Csanad Nemeth, Tamas Univ Szeged Dept Informat Arpad 2 H-6720 Szeged Hungary Mora Ferenc Highsch H-6724 Szeged Hungary

ISBN: (纸本)9783540744559

In this work we investigate such online algorithms for the data acknowledgement problem, which have extra information about the arrival time of the packets in the following time interval of length c. We present an algorithm with the smallest possible competitive ratio for the maximum of delay type objective function. In the case of the sum of delay type objective function we present an 1+O(1/c)-competitive algorithm. Moreover we show that no algorithm may have smaller competitive ratio than 1 + ohm(1/c(2)) in the case of that objective function.

关键词： online algorithms lookahead data acknowledgement

来源：评论

学校读者我要写书评

暂无评论

online State Exploration: Competitive Worst Case and Learning-Augmented algorithms

Online State Exploration: Competitive Worst Case and Learnin...

引用

5th International Workshop on Learning with Imbalanced Domains - Theory and Applications / European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)

作者： Im, Sungjin Moseley, Benjamin Xu, Chenyang Zhang, Ruilong Univ Calif Merced Elect Engn & Comp Sci Merced CA 95343 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA East China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai Peoples R China Univ Buffalo Dept Comp Sci & Engn Buffalo NY 14068 USA

ISBN: (纸本)9783031434204;9783031434211

This paper introduces the online state exploration problem. In the problem, there is a hidden d-dimensional target state. We are given a distance function between different states in the space and a penalty function depending on the current state for each incorrect guess. The goal is to move to a vector that dominates the target state starting from the origin in the d-dimensional space while minimizing the total distance and penalty cost. This problem generalizes several natural online discrete optimization problems such as multi-dimensional knapsack cover, cow path, online bidding, and online search. For online state exploration, the paper gives results in the worst-case competitive analysis model and in the online algorithms augmented with the prediction model. The results extend and generalize many known results in the online setting.

关键词： online Search online algorithms Competitive Ratio Learning-augmented algorithms Worst-case Analysis

来源：评论

学校读者我要写书评

暂无评论

Competitive algorithms for online Multidimensional Knapsack Problems 22

Competitive Algorithms for Online Multidimensional Knapsack ...

引用

2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS/PERFORMANCE 2022

作者： Yang, Lin Zeynali, Ali Hajiesmaili, Mohammad H. Sitaraman, Ramesh K. Towsley, Don University of Massachusetts Amherst AmherstMA United States Akamai Technologies AmherstMA United States

ISBN: (纸本)9781450391412

In this work, we study the online multidimensional knapsack problem (called OMdKP) in which there is a knapsack whose capacity is represented in m dimensions, each dimension could have a different capacity. Then, n items with different scalar profit values and m-dimensional weights arrive in an online manner and the goal is to admit or decline items upon their arrival such that the total profit obtained by admitted items is maximized and the capacity of knapsack across all dimensions is respected. This is a natural generalization of the classic single-dimension knapsack problem with several relevant applications such as in virtual machine allocation, job scheduling, and all-or-nothing flow maximization over a graph. We develop an online algorithm for OMdKP that uses an exponential reservation function to make online admission decisions. Our competitive analysis shows that the proposed online algorithm achieves the competitive ratio of O(log ( a)), where a is the ratio between the aggregate knapsack capacity and the minimum capacity over a single dimension and ? is the ratio between the maximum and minimum item unit values. We also show that the competitive ratio of our algorithm with exponential reservation function matches the lower bound up to a constant factor. © 2022 Owner/Author.

关键词： multidimensional knapsack online algorithms competitive ratio

来源：评论

学校读者我要写书评

暂无评论

History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures

引用

SIGMOD RECORD 2025年第1期54卷 17-26页

作者： Bender, Michael A. Farach-Colton, Martin Goodrich, Michael T. Komlos, Hanna SUNY Stony Brook Stony Brook NY 11794 USA RelationalAI Berkeley CA 94704 USA NYU New York NY USA Univ Calif Irvine Irvine CA USA

A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence is typically viewed as a security or privacy guarantee, with the intent being to minimize risks incurred by a security breach or audit. Despite widespread advances in history independence, there is an important data-structural primitive that previous work has been unable to replace with an equivalent history-independent alternative-dynamic partitioning. In dynamic partitioning, we are given a dynamic set S of ordered elements and a size-parameter B, and the objective is to maintain a partition of S into ordered groups, each of size Theta(B). Dynamic partitioning is important throughout computer science, with applications to B-tree rebalancing, write-optimized dictionaries, log-structured merge trees, other external-memory indexes, geometric and spatial data structures, cache-oblivious data structures, and order-maintenance data structures. The lack of a history independent dynamic-partitioning primitive has meant that designers of history-independent data structures have had to resort to complex alternatives. In this paper, we achieve history-independent dynamic partitioning. Our algorithm runs asymptotically optimally against an oblivious adversary, processing each insert/delete with O (1) operations in expectation and O (B log N/ loglog N) with high probability in set size N.

关键词： algorithms data structures external memory history independence online algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

online Bin Stretching: algorithms and Computer Lower Bounds

Online Bin Stretching: Algorithms and Computer Lower Bounds

引用

作者： Böhm, Martin Charles University of Prague

online Bin Stretching: algorithms and Computer Lower Bounds Author: Martin Böhm Abstract: We investigate a problem in semi-online algorithm design, called online Bin Stretching. The problem can be understood as an online repacking problem: the goal of the algorithm is to repack items of various sizes into m containers of identical size R > 1. The input items arrive one by one and the algorithm must assign an item to a container before the next item arrives. A specialty of this problem is that there is a specific guarantee made to the algorithm: the algorithm learns at the start of the input that there exists a packing of all input items into m containers of capacity 1. Our goal is to design algorithms for this problem which successfully pack the entire incoming sequence one by one while requiring the lowest container capacity R possible. In this thesis, we show several new results about online Bin Stretching: First, we design an algorithm that is able to pack the entire input into m containers of capacity 1.5 regardless of what the vale of m will be. Second, we show a specialized algorithm for the setting of just 3 containers; this algorithm is able to pack into 3 bins of capacity 1.375. Finally, we design and implement an involved search algorithm which is able to find lower bounds for online Bin...

关键词： online algorithms approximation algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：