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

The Stable Roommates Problem with Short Lists

THEORY OF COMPUTING SYSTEMS 2019年第1期63卷 128-149页

作者： Cseh, Agnes Irving, Robert W. Manlove, David F. Hungarian Acad Sci Inst Econ Budapest Hungary Corvinus Univ Budapest Dept Operat Res & Actuarial Sci Budapest Hungary Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland

We consider two variants of the classical Stable Roommates problem with Incomplete (but strictly ordered) preference lists (sri) that are degree constrained, i.e., preference lists are of bounded length. The first variant, egald-sri, involves finding an egalitarian stable matching in solvable instances of sri with preference lists of length at most d. We show that this problem is NP-hard even if d = 3. On the positive side we give a 2d+37-approximation algorithm for d {3,4,5} which improves on the known bound of 2 for the unbounded preference list case. In the second variant of sri, called d-srti, preference lists can include ties and are of length at most d. We show that the problem of deciding whether an instance of d-srti admits a stable matching is NP-complete even if d = 3. We also consider the most stable version of this problem and prove a strong inapproximability bound for the d = 3 case. However for d = 2 we show that the latter problem can be solved in polynomial time.

关键词： Stable matching Bounded length preference lists Complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Randomized algorithms for Some Hard-to-Solve Problems of Clustering a Finite Set of Points in Euclidean Space

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2019年第5期59卷 842-850页

作者： Kel'manov, A. V. Panasenko, A. V. Khandeev, V. I. Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

Two strongly NP-hard problems of clustering a finite set of points in Euclidean space are considered. In the first problem, given an input set, we need to find a cluster (i.e., a subset) of given size that minimizes the sum of the squared distances between the elements of this cluster and its centroid (geometric center). Every point outside this cluster is considered a singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum, over both clusters, of weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of one of the clusters is unknown and is determined as its centroid, while the center of the other cluster is set at some point of space (without loss of generality, at the origin). The weighting factors for both intracluster sums are the given cluster sizes. Parameterized randomized algorithms are presented for both problems. For given upper bounds on the relative error and the failure probability, the parameter value is defined for which both algorithms find approximation solutions in polynomial time. This running time is linear in the space dimension and the size of the input set. The conditions are found under which the algorithms are asymptotically exact and their time complexity is linear in the space dimension and quadratic in the input set size.

关键词： partitioning sequence Euclidean space minimum sum-of-squared distances NP-hardness approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On index policies for stochastic minsum scheduling

引用

OPERATIONS RESEARCH LETTERS 2019年第3期47卷 213-218页

作者： Eberle, Franziska Fischer, Felix Matuschke, Jannik Megow, Nicole Univ Bremen Dept Math & Comp Sci Bremen Germany Queen Mary Univ London Sch Math Sci London England Katholieke Univ Leuven Res Ctr Operat Management Leuven Belgium

Minimizing the sum of completion times when scheduling jobs on m identical parallel machines is a fundamental scheduling problem. Unlike the well-understood deterministic variant, it is a major open problem how to handle stochastic processing times. We show for the prominent class of index policies that no such policy can achieve a distribution-independent approximation factor. This strong lower bound holds even for simple instances with deterministic and two-point distributed jobs. For such instances, we give an O(m)-approximative list scheduling policy. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Stochastic scheduling Parallel machines Total completion time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Better approximability results for min-max tree/cycle/path cover problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期37卷 563-578页

作者： Yu, Wei Liu, Zhaohui East China Univ Sci & Technol Dept Math 130 Meilong Rd Shanghai 200237 Peoples R China

We study the problem of covering the vertices of an undirected weighted graph with a given number of trees (cycles, paths) to minimize the weight of the maximum weight tree (cycle, path). Improved inapproximability lo... 详细信息

关键词： approximation hardness approximation algorithm Tree cover Cycle cover Path cover Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

Mobile Edge Provision with Flexible Deployment

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2019年第5期12卷 750-761页

作者： Hao, Pingting Hu, Liang Jiang, Jingyan Hu, Jiejun Che, Xilong Jilin Univ Coll Comp Sci Changchun 130000 Jilin Peoples R China

The Mobile Edge Network (MEN) has emerged as the basic infrastructure to support fifth-generation networks, mobile edge computing and fog computing. The characteristics of mobility must be addressed to guarantee the quality of service in MENs. As one of the critical problems in MENs, flexible deployment plays a part in exploiting edge networks. Despite the abundance of recently proposed strategies, most concentrate on the change in user demands and inevitably ignore the influence for the user mobility, which is common in future networks. We propose Provision for Mobile Edge Computing (PMEC), a prototype that takes advantage of storage devices with flexible placement. In PMEC, we accommodate various considerations and select different storage devices to cache, deploying the cache with the relationship of a two-tiered structure in the MEN. Thus, we construct a flexible overlay network with the objective of minimizing the cost in a two-tiered edge network. Based on the analysis of the problem, we solve the two-tiered placement from bottom to top using the dynamic minimal spanning tree (MST) algorithm and design two algorithms for each tier including the basic algorithm and the improved algorithms. The simulation is conducted on realistic data to demonstrate the performance of our algorithms.

关键词： Servers Heuristic algorithms approximation algorithms Edge computing Computer architecture Computational modeling Optimization Mobile edge computing optimization modeling placement approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Multi-Antennae Largest Weight Data Retrieval

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2017年第12期16卷 3320-3333页

作者： Guo, Longkun Shen, Hong Zhu, Wenxing Fuzhou Univ Coll Math & Comp Sci Fuzhou Fujian Peoples R China Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Yat Sen Univ Sch Informat Sci & Technol Guangzhou Guangdong Peoples R China

In a mobile network, wireless data broadcast over m channels (frequencies) is a powerful means for distributed dissemination of data to clients who access the channels through multi-antennae equipped on their mobile devices. The delta-antennae largest weight data retrieval (delta ALWDR) problem is to compute a schedule for downloading a subset of data items that has a maximum total weight using delta antennae in a given time interval. In this paper, we first give a linear programming (LP) relaxation for delta ALWDR and show that it is polynomial-time solvable when every data item appears at most once. We also show that when there exist data items with multiple occurrences, the integrality gap of this LP formula is 2. We then present an approximation algorithm of ratio 1 - 1/e for the delta-antennae gamma-separated largest weight data retrieval (delta A gamma LWDR) problem, a weaker version of delta ALWDR where each block of up to gamma data (time) slots is separated by a vacant slot on all channels, applying the techniques called collectively randomized LP rounding and layered DAG construction. We show that delta A gamma LWDR is NP-complete even for the simple case of gamma = 2, m = 3, and equal-weight data items each appearing up to 3 times. Our algorithm runs in time O(2(gamma)m(7)T(3.5)L), where T is the number of time slots, and L is the maximum length of the input. Then, from the simple observation that a ratio alpha approximation solution to delta A gamma LWDR implies a ratio alpha - is an element of approximation solution to delta ALWDR for any fixed is an element of > 0, we immediately have an approximation algorithm of ratio 1 - 1/e - is an element of for delta ALWDR. Our algorithm has the same approximation ratio as the known result in [15] which holds only for delta = 1, with a significantly lower time complexity of O(2(1/is an element of)1/is an element of m(7)T(3.5)L) (improved from O(is an element of(3.5) m(3.5/)is an element of(TL)-L-3.5) . As a by-pr

关键词： Distributed data dissemination multi-antennae data retrieval scheduling approximation algorithm linear programming

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for the Bounded Flexible Scheduling Problem in Clouds

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第12期28卷 3511-3520页

作者： Guo, Longkun Shen, Hong Fuzhou Univ Coll Math & Comp Sci Fuzhou 350002 Fujian Peoples R China Univ Adelaide Sch Comp Sci Adelaide SA 5005 Australia Sun Yat Sen Univ Sch Informat Sci & Technol Guangzhou 510275 Guangdong Peoples R China

Clouds, such as Amazon Infrastructure-as-a-Service (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resource-efficiency scheduling. The bounded flexible scheduling (BFS) problem is one of the problems proposed to meet such requirements. In BFS, we are given a set of identical machines and a set of jobs, each of which is with a value, a workload, a deadline and a parallelism degree, i.e., the maximum number of machines on which the job can execute concurrently. The problem is to compute an assignment of the given jobs to the machines, such that the total value of the jobs successfully completed by their deadlines is maximized. This paper presents a factor-C-k/C approximation algorithm for BFS, where k is the maximum parallelism degree and C is the capacity of the system(i.e., the number of machines). Since C >> k in BFS, our result significantly improves the known best approximation ratio of (C-k/2C-k)(1 - is an element of) for tight deadlines [17], and C-k/C . s-1/s for loose deadlines [18] on a slackness ratio s >= 1 that is the maximum ratio between a job's earliest actual finish time and its deadline. We first propose feasibility condition to determine whether an instance of BFS is feasible, i.e., whether there exists a scheduling according to which all jobs can finish before their deadlines, which is the key to achieve the ratio improvement of our algorithm. To prove the correctness of the feasibility condition, we give a simple linear program(LP) for a weaker version of BFS, and show that it is with an integral polyhedron and hence the version of BFS is polynomial-time solvable. Then we present a greedy algorithm and its equivalent primal-dual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C-k/C, and time complexity O(n(2) + nT), where n is the number of jobs and T is the number of time slots. As a by-product, we show that the BFS admits a polynomial-time approximation scheme (PTAS) when T is fix

关键词： approximation algorithm primal dual method bounded flexible scheduling resource allocation

来源：评论

学校读者我要写书评

暂无评论

Visibility testing and counting for uncertain segments

引用

THEORETICAL COMPUTER SCIENCE 2019年 779卷 1-7页

作者： Abam, Mohammad Ali Alipour, Sharareh Ghodsi, Mohammad Mahdian, Mohammad Sherif Univ Technol Comp Engn Dept Tehran Iran Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Google Res Mountain View CA 94043 USA

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R-2, and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s is an element of S visible from the given query point q is an element of R-2 (for visibility testing) and how many segments in S are visible from the given query point q is an element of R-2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment s is an element of S is visible from a given query point q and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in S that are visible from a query point q. We first show that PVTP is #P-complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that PVTP is solvable in O(n logn) time. Our algorithm for PVTP combined with linearity of expectation gives an O(n(2) logn) time algorithm for PVCP. Using the algorithm for PVTP, together with a few old tricks, we can show that one can preprocess S in O(n(5) logn) time into a data structure of size O(n(4)), so that each PVTP query for a fixed segments can be answered in O (logn) time. We also give a faster 2-approximation algorithm for this problem. At the end, we improve the approximation factor of the algorithm. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Computational geometry Visibility Randomized algorithm approximation algorithm Probabilistic segments

来源：评论

学校读者我要写书评

暂无评论

Two-agent scheduling on a single parallel-batching machine to minimize the weighted sum of the agents' makespans

引用

JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING 2019年第3期10卷 999-1007页

作者： Zhang, Cui-Lin Wang, Jun-Qiang Zhang, Cheng-Wu Xian Aeronaut Univ Sch Econ & Management Xian 710077 Shaanxi Peoples R China Northwestern Polytech Univ Performance Anal Ctr Prod & Operat Syst PacPos Xian 710072 Shaanxi Peoples R China Northwestern Polytech Univ Minist Educ Key Lab Contemporary Design & Integrated Mfg Tech Xian 710072 Shaanxi Peoples R China

We schedule the jobs from two agents with equal processing times and non-identical job sizes on a single parallel-batching machine. The objective is to minimize the weighted sum of the two makespans of the jobs from two agents. We give a lower bound on the optimal solution, and present a polynomial-time algorithm H for solving the problem. Furthermore, we prove that both the absolute worst-case ratio and the asymptotic worst-case ratio of algorithm H are the functions of the weight of one agent, . Specifically, (1) for the absolute worst-case ratio, H(I)f1()xOPT(I), where f1()=(3-3+32)/(2-4+42)9/4;(2) for the asymptotic worst-case ratio, H(I)f2()xOPT(I)+4/3, where f2()=(11-11+112)/(9-18+182) and 11/9f2()11/6. The effectiveness of algorithm H is demonstrated by using a set of computational experiments. The results show that algorithm H performs well in practice and tends to perform better when facing the large-scale instances.

关键词： Two-agent scheduling Parallel-batching machine Makespan Lower bound approximation algorithm Worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

Split Packing: algorithms for Packing Circles with Optimal Worst-Case Density

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2019年第3期61卷 562-594页

作者： Fekete, Sandor P. Morr, Sebastian Scheffer, Christian Braunschweig Univ Technol Dept Comp Sci Algorithms Grp Muhlenpfordtstr 23 D-38106 Braunschweig Germany

In the classic, -hard circle packing problem, one asks whether a given set of circles can be packed into a given container. In this paper, we present new sufficient conditions for packing circles into square and triangular containers, using only the sum of the circles' areas: for square containers, it is possible to pack any set of circles with a combined area of up to of the square's area. And when the container is a right or obtuse triangle, any set of circles whose combined area does not exceed the triangle's incircle can be packed. These area conditions are tight: for any larger areas, there are sets of circles which cannot be packed. Similar results have long been known for squares, but to the best of our knowledge, we give the first results of this type for circular objects. Our proofs are constructive: we describe a versatile, divide-and-conquer-based algorithm for packing circles into various container shapes with optimal worst-case density, which employs an elegant, recursive subdivision scheme. We call this algorithm Split Packing. It can be used as a constant-factor approximation algorithm when looking for the smallest container in which a given set of circles can be packed, due to its polynomial runtime. A visualization can be found at https://***/split-packing/.

关键词： Circle packing Worst-case analysis approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：