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

online Minimization of the Maximum Starting Time: Migration Helps

ALGORITHMICA 2023年第8期85卷 2238-2259页

作者： Levin, Asaf The Technion Fac Ind Engn & Management IL-32000 Haifa Israel

We consider non-preemptive load balancing on m identical machines where the cost of amachine is defined as the maximum starting time of a job assigned to the machine, and the goal is to find a partition of the jobs that minimizes the maximum machine cost. In our variant the last job on each machine is the smallest job assigned to that machine. The online model for this problem is too restrictive as a trivial example shows that there is no competitive algorithm for the problem. We show that a constant migration factor is sufficient to guarantee a (3/2 +epsilon)-competitive algorithm for all epsilon > 0, and using a constant migration factor cannot lead to a better than a 3/2-competitive algorithm. We also show that for this problem, constant amortized migration factor is strictly more powerful and allows us to obtain a polynomial time approximation scheme with a constant amortized migration factor. Thus, the ability to move some limited set of jobs on each step allows the algorithm to be much better than in the pure online settings.

关键词： online algorithms Scheduling Migration factor

来源：评论

学校读者我要写书评

暂无评论

online Combinatorial Assignment in Independence Systems 25th

Online Combinatorial Assignment in Independence Systems

引用

25th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Marinkovic, Javier Soto, Jose A. Verdugo, Victor Univ Chile Dept Math Engn Santiago Chile Univ Chile Ctr Math Modeling IRL CNRS 2807 Santiago Chile Pontificia Univ Catalica Chile Inst Math & Computat Engn Santiago Chile Pontificia Univ Catalica Chile Dept Ind & Syst Engn Santiago Chile

ISBN: (纸本)9783031598340;9783031598357

We consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an item to be sold, and every edge represents a bundle of items. For combinatorial auctions, Kesselheim et al. showed upper bounds of O(log log(k)/ log(k)) and O(log log(n)/ log(n)) on the competitiveness of any online algorithm, even in the random order model, where k is the maximum bundle size and n is the number of items. We provide an exponential improvement by giving upper bounds of O(log(k)/k), and O(log(n)/root n) for the prophet IID setting. Furthermore, using linear programming, we provide new and improved guarantees for the k-bounded online combinatorial auction problem (i.e., bundles of size at most k). We show a (1-e(-k))/k-competitive algorithm in the prophet IID model, a 1/(k + 1)-competitive algorithm in the prophet-secretary model using a single sample per agent, and a k(-k/(k-1))-competitive algorithm in the secretary model. Our algorithms run in polynomial time and work in more general independence systems where the offline combinatorial assignment problem admits the existence of a polynomial-time randomized algorithm that we call certificate sampler. These systems include some classes of matroids, matroid intersections, and matchoids.

关键词： online algorithms Linear Programming Combinatorial Auctions

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for online metric b-matching

引用

OPERATIONS RESEARCH LETTERS 2023年第6期51卷 591-594页

作者： Kalyanasundaram, Bala Pruhs, Kirk Stein, Cliff Georgetown Univ Dept Comp Sci Washington DC 20056 USA Univ Pittsburgh Comp Sci Dept Pittsburgh PA 15260 USA Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA Columbia Univ Dept IEOR New York NY 10027 USA

We give a randomized algorithm for online metric b-matching that is O (log2 k) competitive, where k is the number of server locations, by giving a black box reduction from b-matching on a hierarchically separated tree... 详细信息

关键词： Matching online algorithms Metric matching

来源：评论

学校读者我要写书评

暂无评论

online Dominant Generalized Eigenvectors Extraction via a Randomized Algorithm

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2023年第6期72卷 7597-7612页

作者： Cai, Haoyuan Kaloorazi, Maboud Chen, Jie Chen, Wei Richard, Cedric Northwestern Polytech Univ Shenzhen Res & Dev Inst Shenzhen 518063 Peoples R China Northwestern Polytech Univ Sch Marine Sci & Technol Xian 710072 Peoples R China Beijing Jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China Univ Cote Azur F-06000 Nice France

This paper is concerned with online algorithms for the generalized Hermitian eigenvalue problem (GHEP). We first present an algorithm based on randomization, termed alternate-projections randomized eigenvalue decomposition (APR-EVD), to solve the standard eigenvalue problem. The APR-EVD algorithm is computationally efficient and can be computed by making only one pass through the input matrix. We then develop two online algorithms based on APR-EVD for the dominant generalized eigenvectors extraction. Our proposed algorithms use the fact that GHEP is transformed into a standard eigenvalue problem, however to avert computations of a matrix inverse and inverse of the square root of a matrix, which are prohibitive, they exploit the rank-1 strategy for the transformation. Our algorithms are devised for extracting generalized eigenvectors for scenarios in which observed stochastic signals have unknown covariance matrices. The effectiveness and practical applicability of our proposed algorithms are validated through numerical experiments with synthetic and real-world data.

关键词： Dominant generalized eigenvector extraction fast subspace estimation and tracking matrix decomposition online algorithms Randomized algorithms real-time hyperspectral image denoising

来源：评论

学校读者我要写书评

暂无评论

Removable online Knapsack with Bounded Size Items 49th

Removable Online Knapsack with Bounded Size Items

引用

49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Gourves, Laurent Pagourtzis, Aris Univ Paris Dauphine PSL CNRS LAMSADE F-75016 Paris France Natl Tech Univ Athens Zografos 15780 Greece Athena RC Archimedes Res Unit Maroussi 15125 Greece

ISBN: (纸本)9783031521126;9783031521133

In the online unweighted knapsack problem, some items arrive in sequence and one has to decide to pack them or not into a knapsack of given capacity. The objective is to maximize the total size of packed items. In the traditional setting, decisions are irrevocable, and the problem cannot admit any rho-competitive algorithm. The removable nature of the items allows to withdraw previously packed elements of the current solution. This feature makes the online knapsack problem amenable to competitive analysis under the ratio of (root 5 - 1)/2, which is at the same time the best possible performance guarantee [12]. This article deals with refinements of the best possible competitive ratio of the online unweighted knapsack problem with removable items when either an upper or a lower bound on the size of the items is known.

关键词： online algorithms Knapsack Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Optimal Resource Management in Dynamic D2D Communications 10

Online Algorithms for Optimal Resource Management in Dynamic...

引用

10th International Conference on Mobile Ad-hoc and Sensor Networks MSN

作者： Kuhnle, Alan Li, Xiang Thai, My T. Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

ISBN: (纸本)9781479973941

Device-to-device (D2D) communications has recently emerged as a promising technology for boosting the capacity of cellular systems. D2D enables direct communication between mobile devices over the cellular band without utilizing infrastructure nodes such as base stations, thereby reducing the load on cellular base stations and increasing network throughput through spatial reuse of radio resources. Hence it is important to optimally allocate these radio resources. Furthermore, since the composition of a cellular macrocell is highly dynamic, it is critical to adaptively update the resource allocation for D2D communications rather than recomputing it from scratch. In this work, we develop the first online algorithm, namely ODSRA, for dynamic resource allocation while maximizing spatial reuse. At the core of the resource allocation problem is the online set multicover problem, for which we present the first deterministic O (log n log m)-competitive online algorithm, where n is the number of elements, and m the number of sets. By simulation, we show the efficacy of ODSRA by analyzing network throughput and other metrics, obtaining a large improvement in running time over offline methods.

关键词： D2D communications online algorithms resource allocation spatial reuse

来源：评论

学校读者我要写书评

暂无评论

O(1/ε) Is the Answer in online Weighted Throughput Maximization 41

O(1/ε) Is the Answer in Online Weighted Throughput Maximiza...

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Eberle, Franziska Techn Univ Berlin Berlin Germany

ISBN: (纸本)9783959773119

We study a fundamental online scheduling problem where jobs with processing times, weights, and deadlines arrive online over time at their release dates. The task is to preemptively schedule these jobs on a single or multiple (possibly unrelated) machines with the objective to maximize the weighted throughput, the total weight of jobs that complete before their deadline. To overcome known lower bounds for the competitive analysis, we assume that each job arrives with some slack epsilon> 0;that is, the time window for processing job j on any machine i on which it can be executed has length at least (1 + epsilon) times j's processing time on machine i. Our contribution is a best possible online algorithm for weighted throughput maximization on unrelated machines: Our algorithm is O (1/epsilon-competitive, which matches the lower bound for unweighted throughput maximization on a single machine. Even for a single machine, it was not known whether the problem with weighted jobs is "harder" than the problem with unweighted jobs. Thus, we answer this question and close weighted throughput maximization on a single machine with a best possible competitive ratio Theta (1-epsilon). While we focus on non-migratory schedules, on identical machines, our algorithm achieves the same (up to constants) performance guarantee when compared to an optimal migratory schedule.

关键词： Deadline scheduling weighted throughput online algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online Clustering on the Line with θ-th Power Cost Variable Sized Clustering 42nd

Online Clustering on the Line with θ-th Power Cost Variable...

引用

42nd National Conference on Theoretical Computer Science

作者： Luo, Rongchuan Yunnan Univ Sch Math & Stat Kunming 650000 Yunnan Peoples R China

ISBN: (纸本)9789819614899;9789819614905

online clustering is the process of dynamically partitioning a set of points into clusters in a sequential manner, where points arrive one after another and are assigned to clusters upon arrival. We focus on the one-dimensional clustering scenario, where the cost of a cluster is the unit cost of opening cluster 1 plus the theta-th power cost of the cluster diameter. The objective is to minimize the total cost incurred by the algorithm in opening clusters. We investigate both the strict model and the flexible model, both of which maintain two essential properties: points allocated to a given cluster must remain assigned to that cluster, and clusters cannot be merged or split. In the strict model, cluster diameters and precise positions are predetermined during the initialization of clusters. In the flexible model, the algorithm has the flexibility to move or expand clusters, as long as points allocated to a cluster remain assigned to that cluster. This paper introduces the GRID(a) algorithm for the strict model's online problem and the SOSMa algorithm for the semi-online problem, providing proofs of their approximation ratios. For the flexible model's online problem, we present the FGRID(a) algorithm and establish its approximation ratio.

关键词： online algorithms Competitive analysis Clustering problem

来源：评论

学校读者我要写书评

暂无评论

online Stochastic Matching: New algorithms and Bounds

引用

ALGORITHMICA 2020年第10期82卷 2737-2783页

作者： Brubach, Brian Sankararaman, Karthik Abinav Srinivasan, Aravind Xu, Pan Univ Maryland College Pk MD 20742 USA New Jersey Inst Technol Newark NJ 07102 USA

online matching has received significant attention in recent years due to its close connection to Internet advertising. As the seminal work of Karp, Vazirani, and Vazirani has an optimal (1 - 1/ ) competitive ratio in the standard adversarial online model, much effort has gone into developing useful online models that incorporate some stochasticity in the arrival process. One such popular model is the "known I.I.D. model" where different customer-types arrive online from a known distribution. We develop algorithms with improved competitive ratios for some basic variants of this model with integral arrival rates, including: (a) the case of general weighted edges, where we improve the best-known ratio of 0.667 due to Haeupler, Mirrokni and Zadimoghaddam (WINE, 2011) to 0.705;and (b) the vertexweighted case, where we improve the 0.7250 ratio of Jaillet and Lu (Math Oper Res 39(3):624-646, 2013) to 0.7299. We also consider an extension of stochastic rewards, a variant where each edge has an independent probability of being present. For the setting of stochastic rewards with non-integral arrival rates, we present a simple optimal non-adaptive algorithm with a ratio of 1 - 1/ . For the special case where each edge is unweighted and has a uniform constant probability of being present, we improve upon 1 - 1/ by proposing a strengthened LP benchmark. One of the key ingredients of our improvement is the following (offline) approach to bipartite-matching polytopes with additional constraints. We first add several valid constraints in order to get a good fractional solution;however, these give us less control over the structure of . We next remove all these additional constraints and randomly move from to a feasible point on the matching polytope with all coordinates being from the set {0, 1/k, 2/k,., 1} for a chosen integer k. The structure of this solution is inspired by Jaillet and Lu (2013) and is a tractable structure for algorithm design and analysis. The appropriate rand

关键词： online algorithms Randomized algorithms Bipartite matching Internet advertising

来源：评论

学校读者我要写书评

暂无评论

The online Submodular Assignment Problem 65

The Online Submodular Assignment Problem

引用

65th Symposium on Foundations of Computer Science

作者： Hathcock, Daniel Jin, Billy Patton, Kalen Sarkar, Sherry Zlatin, Michael Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Univ Chicago Booth Sch Business Chicago IL 60637 USA Georgia Tech Sch Math Atlanta GA USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

ISBN: (纸本)9798331516758;9798331516741

online resource allocation is a rich and varied field. One of the most well-known problems in this area is online bipartite matching, introduced in 1990 by Karp, Vazirani, and Vazirani. Since then, many variants have been studied, including AdWords, the generalized assignment problem (GAP), and online submodular welfare maximization. In this paper, we introduce a generalization of GAP which we call the submodular assignment problem (SAP). This generalization captures many online assignment problems, including all classical online bipartite matching problems as well as broader online combinatorial optimization problems such as online arboricity, flow scheduling, and laminar restricted allocations. We present a fractional algorithm for online SAP that is (1 - 1/e)-competitive. Additionally, we study several integral special cases of the problem. In particular, we provide a (1 - 1/e - epsilon)-competitive integral algorithm under a small-bids assumption, and a (1 - 1/e)-competitive integral algorithm for online submodular welfare maximization where the utility functions are given by rank functions of matroids. The key new ingredient for our results is the construction and structural analysis of a "water level" vector for polymatroids, which allows us to generalize the classic water-filling paradigm used in online matching problems. This construction reveals connections to submodular utility allocation markets and principal partition sequences of matroids.

关键词： Combinatorial Optimization online algorithms Bipartite Matching Adwords Submodular Functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：