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

31st International Symposium on algorithms and Computation, ISAAC 2020

作者： Nguyen, Trung Thanh Rothe, Jörg ORLab Faculty of Computer Science Phenikaa University Hanoi12116 Viet Nam Institut für Informatik Heinrich-Heine-Universität Düsseldorf Germany

ISBN: (纸本)9783959771733

We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires pi,j time units and incurs a cost ci,j, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [15], we construct a more general approach that can be used to derive approximation schemes to a wider class of load balancing problems with constraints. © Trung Thanh Nguyen and Jörg Rothe.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Conditionally optimal approximation algorithms for the girth of a directed graph 47

Conditionally optimal approximation algorithms for the girth...

引用

47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

作者： Dalirrooyfard, Mina Williams, Virginia Vassilevska MIT CambridgeMA United States

ISBN: (纸本)9783959771382

The girth is one of the most basic graph parameters, and its computation has been studied for many decades. Under widely believed fine-grained assumptions, computing the girth exactly is known to require mn1−o(1) time, both in sparse and dense m-edge, n-node graphs, motivating the search for fast approximations. Fast good quality approximation algorithms for undirected graphs have been known for decades. For the girth in directed graphs, until recently the only constant factor approximation algorithms ran in O(nω) time, where ω 1−Ε) time for Ε > 0 and all sparsities m was only recently obtained by Chechik et al. [STOC 2020];it is also combinatorial. It is known that a better than 2-approximation algorithm for the girth in dense directed unweighted graphs needs n3−o(1) time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in O(mn1−Ε) time (by Chechik et al.) is 3. Is the true answer 2 or 3? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least mn1−o(1) time for some sparsity m if it achieves a (2 − Ε)-approximation for any Ε > 0. Second we give a 2-approximation algorithm for the girth of unweighted graphs running in Õ(mn3/4) time, and a (2 + Ε)-approximation algorithm (for any Ε > 0) that works in weighted graphs and runs in Õ(m√n) time. Our algorithms are combinatorial. We also obtain a (4+Ε)-approximation of the girth running in Õ(mn√2−1) time, improving upon the previous best Õ(m√n) running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a (5 + Ε)-approximate roundtrip spanner on Õ(n1.5/Ε2) edges in Õ(m√n/Ε2) time. This improves upon the previous approximation factor (8 + Ε) of Chechik et al. for the same running time. © Mina Dalirrooyfard and V

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for clustering with dynamic points

arXiv

引用

arXiv 2020年

作者： Deng, Shichuan Li, Jian Rabani, Yuval Tsinghua University China The Hebrew University of Jerusalem Israel

We study two generalizations of classic clustering problems called dynamic ordered k-median and dynamic k-supplier, where the points that need clustering evolve over time, and we are allowed to move the cluster centers between consecutive time steps. In these dynamic clustering problems, the general goal is to minimize certain combinations of the service cost of points and the movement cost of centers, or to minimize one subject to some constraints on the other. We obtain a constant-factor approximation algorithm for dynamic ordered k-median under mild assumptions on the input. We give a 3-approximation for dynamic k-supplier and a multi-criteria approximation for its outlier version where some points can be discarded, when the number of time steps is two. We complement the algorithms with almost matching hardness results. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight approximation algorithms for p-mean welfare under subadditive valuations 28

Tight approximation algorithms for p-mean welfare under suba...

引用

28th Annual European Symposium on algorithms, ESA 2020

作者： Barman, Siddharth Bhaskar, Umang Krishna, Anand Sundaram, Ranjani G. Indian Institute of Science Bangalore India Tata Institute of Fundamental Research Mumbai India Chennai Mathematical Institute India

ISBN: (纸本)9783959771627

We develop polynomial-time algorithms for the fair and efficient allocation of indivisible goods among n agents that have subadditive valuations over the goods. We first consider the Nash social welfare as our objective and design a polynomial-time algorithm that, in the value oracle model, finds an 8n-approximation to the Nash optimal allocation. Subadditive valuations include XOS (fractionally subadditive) and submodular valuations as special cases. Our result, even for the special case of submodular valuations, improves upon the previously best known O(n log n)-approximation ratio of Garg et al. (2020). More generally, we study maximization of p-mean welfare. The p-mean welfare is parameterized by an exponent term p ∈ (−∞, 1] and encompasses a range of welfare functions, such as social welfare (p = 1), Nash social welfare (p → 0), and egalitarian welfare (p → −∞). We give an algorithm that, for subadditive valuations and any given p ∈ (−∞, 1], computes (in the value oracle model and in polynomial time) an allocation with p-mean welfare at least 1/8n times the optimal. Further, we show that our approximation guarantees are essentially tight for XOS and, hence, subadditive valuations. We adapt a result of Dobzinski et al. (2010) to show that, under XOS valuations, an O (n1-Ε) approximation for the p-mean welfare for any p ∈ (−∞, 1] (including the Nash social welfare) requires exponentially many value queries;here, Ε > 0 is any fixed constant. © Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A unified framework of FPT approximation algorithms for clustering problems 31

A unified framework of FPT approximation algorithms for clus...

引用

31st International Symposium on algorithms and Computation, ISAAC 2020

作者： Feng, Qilong Zhang, Zhen Huang, Ziyun Xu, Jinhui Wang, Jianxin School of Computer Science and Engineering Central South University Changsha China Department of Computer Science and Software Engineering Penn State Erie The Behrend College PA United States Department of Computer Science and Engineering State University of New York Buffalo United States

ISBN: (纸本)9783959771733

In this paper, we present a framework for designing FPT approximation algorithms for many k-clustering problems. Our results are based on a new technique for reducing search spaces. A reduced search space is a small subset of the input data that has the guarantee of containing k clients close to the facilities opened in an optimal solution for any clustering problem we consider. We show, somewhat surprisingly, that greedily sampling O(k) clients yields the desired reduced search space, based on which we obtain FPT(k)-time algorithms with improved approximation guarantees for problems such as capacitated clustering, lower-bounded clustering, clustering with service installation costs, fault tolerant clustering, and priority clustering. © Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Probabilistic k-Center Clustering

Approximation Algorithms for Probabilistic k-Center Clusteri...

引用

IEEE International Conference on Data Mining (ICDM)

作者： Sharareh Alipour School of computer science Institute for research in fundamental sciences IPM Tehran Iran

ISBN: (数字)9781728183169

ISBN: (纸本)9781728183176

Uncertainty about data appears in many realworld applications and an important issue is how to manage, analyze and solve optimization problems over such data. An important tool for data analysis is clustering. When the data set is uncertain, we can model them as a set of probabilistic points each formalized as a probability distribution function which describes the possible locations of the points. In this paper, we study k-center problem for probabilistic points in a general metric space. First we present a fast greedy approximation algorithm that builds k centers using a farthest-first traversal in k iterations. This algorithm improves the previous approximation factor of the unrestricted assigned k-center problem from 10 (see [1]) to 6. Next we restrict the centers to be selected from all the probabilistic locations of the given points and we show that an optimal solution for this restricted setting is a 2-approximation factor solution for an optimal solution of the assigned k-center problem with expected distance assignment. Using this idea, we improve the approximation factor of the unrestricted assigned k-center problem to 4 by increasing the running time. The algorithm also runs in polynomial time when k is a constant. Additionally, we implement our algorithms on three real data sets. The experimental results show that in practice the approximation factors of our algorithms are better than in theory for these data sets. Also we compare the results of our algorithm with the previous works and discuss about the achieved results.

关键词： Uncertainty Clustering algorithms Tools approximation algorithms Probabilistic logic Extraterrestrial measurements Probability distribution

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Distributed Multi-Robot Coverage in Non-Convex Environments

arXiv

引用

arXiv 2020年

作者： Sadeghi, Armin Asghar, Ahmad Bilal Smith, Stephen L. Department of Electrical and Computer Engineering University of Waterloo WaterlooON Canada

In this paper, we revisit the distributed coverage control problem with multiple robots on both metric graphs and in non-convex continuous environments. Traditionally, the solutions provided for this problem converge to a locally optimal solution with no guarantees on the quality of the solution. We consider sub-additive sensing functions, which capture the scenarios where sensing an event requires the robot to visit the event location. For these sensing functions, we provide the first constant factor approximation algorithms for the distributed coverage problem. The approximation results require twice the conventional communication range in the existing coverage algorithms. However, we show through extensive simulation results that the proposed approximation algorithms outperform several existing algorithms in convex, non-convex continuous, and discrete environments even with the conventional communication ranges. Moreover, the proposed algorithms match the state-of-the-art centralized algorithms in the solution quality. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for scheduling a group of heat pumps

arXiv

引用

arXiv 2020年

作者： Fink, Jiří Department of Theoretical Computer Science and Mathematical Logic Faculty of Mathematics and Physics Charles University in Prague

This paper studies planning problems for a group of heating systems which supply the hot water demand for domestic use in houses. These systems (e.g. gas or electric boilers, heat pumps or microCHPs) use an external energy source to heat up water and store this hot water for supplying the domestic demands. The latter allows to some extent a decoupling of the heat production from the heat demand. We focus on the situation where each heating system has its own demand and buffer and the supply of the heating systems is coming from a common source. In practice, the common source may lead to a coupling of the planning for the group of heating systems. The bottleneck to supply the energy may be the capacity of the distribution system (e.g. the electricity networks or the gas network). As this has to be dimensioned for the maximal consumption, it is important to minimize the maximal peak. This planning problem is known to be NP-hard. We present polynomial-time approximation algorithms for four variants of peak minimization problems, and we determine the worst-case approximation error. Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for partially colorable graphs 22

Approximation algorithms for partially colorable graphs

引用

22nd International Conference on approximation algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019

作者： Ghoshal, Suprovat Louis, Anand Raychaudhury, Rahul Indian Institute of Science Bangalore India

ISBN: (纸本)9783959771252

Graph coloring problems are a central topic of study in the theory of algorithms. We study the problem of partially coloring partially colorable graphs. For α ≤ 1 and k ∈ Z+, we say that a graph G = (V, E) is α-partially k-colorable, if there exists a subset S ⊂ V of cardinality |S| ≥ α|V | such that the graph induced on S is k-colorable. Partial k-colorability is a more robust structural property of a graph than k-colorability. For graphs that arise in practice, partial k-colorability might be a better notion to use than k-colorability, since data arising in practice often contains various forms of noise. We give a polynomial time algorithm that takes as input a (1 − ∊)-partially 3-colorable graph G and a constant γ ∈ [∊, 1/10], and colors a (1 − ∊/γ) fraction of the vertices using Õ (Formula presented.) colors. We also study natural semi-random families of instances of partially 3-colorable graphs and partially 2-colorable graphs, and give stronger bi-criteria approximation guarantees for these family of instances. © Suprovat Ghoshal, Anand Louis, and Rahul Raychaudhury.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Lower bounds and approximation algorithms for search space sizes in contraction hierarchies 28

Lower bounds and approximation algorithms for search space s...

引用

28th Annual European Symposium on algorithms, ESA 2020

作者： Blum, Johannes Storandt, Sabine University of Konstanz Germany

ISBN: (纸本)9783959771627

Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in O(√n) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in O(hlog D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in Ω(b) for α ≥ 2/3 where b is the size of a smallest α-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the O(√n) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network. © Johannes Blum and Sabine Storandt

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：