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

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

来源：评论

学校读者我要写书评

暂无评论

Additive stabilizers for unstable graphs

引用

DISCRETE OPTIMIZATION 2019年 31卷 56-78页

作者： Chandrasekaran, Karthekeyan Gottschalk, Corinna Konemann, Jochen Peis, Britta Schmand, Daniel Wierz, Andreas Univ Illinois Dept Ind & Enterprise Syst Engn Champaign IL USA Rhein Westfal TH Aachen Sch Business & Econ Aachen Germany Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

A weighted graph is called stable if the maximum weight of an integral matching equals the cost of a minimum-weight fractional vertex cover. We address the following question: how can we modify a given unstable graph in the least intrusive manner in order to achieve stability? Previous works have addressed stabilization through addition or deletion of the smallest possible number of edges/vertices. In this work we investigate the following more fine-grained additive stabilization strategy: given a graph G = (V, E) with unit edge weights;find non-negative c is an element of R-E with minimum Sigma(e) c(e) such that adding c(e) to the unit edge weight of each e is an element of E yields a stable graph. We provide the first super-constant hardness of approximation results for any graph stabilization problem: (i) unless the current best-known algorithm for the densest-k-subgraph problem can be improved, there is no o(vertical bar V vertical bar(1/24))- approximation for additive stabilizers;(ii) the additive stabilizer problem has no o(log vertical bar V vertical bar) approximation unless P = NP. On the algorithmic side, we present (iii) a polynomial time algorithm with approximation factor at most root vertical bar V vertical bar for a super-class of the instances generated in our hardness proofs, (iv) an algorithm to solve min additive stabilizer in factorcritical graphs exactly in polynomial time, and (v) an algorithm to solve min additive stabilizer in arbitrary graphs exactly in time exponential in the size of the Tutte set. Our main tools are the Gallai-Edmonds decomposition and structural results for the problem that reduce the continuous decision domain to a discrete decision domain. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Graph stabilization Gallai-Edmonds decomposition Matching Vertex cover approximation algorithm Hardness

来源：评论

学校读者我要写书评

暂无评论

A Generalized Parallel Task Model for Recurrent Real-Time Processes

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2019年第1期6卷 1–40页

作者： Bonifaci, Vincenzo Wiese, Andreas Baruah, Sanjoy K. Marchetti-Spaccamela, Alberto Stiller, Sebastian Stougie, Leen CNR IASI Via Taurini 19 I-00185 Rome Italy Max Planck Inst Informat Saarbrucken Germany Univ N Carolina Comp Sci Dept Chapel Hill NC 27515 USA Sapienza Univ Roma Dipartimento Ingn Informat Automat & Gest Via Ariosto 25 I-00185 Rome Italy Tech Univ Carolo Wilhelmina Braunschweig Braunschweig Germany Tech Univ Braunschweig Inst Math Optimizat Univ Pl 2 D-38106 Braunschweig Germany CWI POB 94079 NL-1090 GB Amsterdam Netherlands Vrije Univ Amsterdam Amsterdam Netherlands Univ Chile Fac Ciencias Fis & Matemat Santiago Ctr Beauchef 851 705 Piso 7 Santiago Chile Washington Univ McKelvey Sch Engn Campus Box 11001 Brookings Dr St Louis MO 63130 USA

A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. A recurrent task is specified as a directed acyclic graph (DAG), a period, and a relative deadline. Each vertex of the DAG represents a sequential job, while the edges of the DAG represent precedence constraints between these jobs. All the jobs of the DAG are released simultaneously and need to complete execution within the specified relative deadline of their release. Each task may release jobs in this manner an unbounded number of times, with successive releases occurring at least the specified period apart. Conditional control structures are also allowed. The scheduling problem is to determine whether a set of such recurrent tasks can be scheduled to always meet all deadlines upon a specified number of identical processors. This problem is shown to be computationally intractable, but amenable to efficient approximate solutions. Earliest Deadline First (EDF) and Deadline Monotonic (DM) are shown to be good approximate global scheduling algorithms. Polynomial and pseudo-polynomial time schedulability tests, of differing effectiveness, are presented for determining whether a given task set can be scheduled by EDF or DM to always meet deadlines on a specified number of processors.

关键词： Precedence constraints multiprocessor platform directed acyclic graph conditional control-flow schedulability test approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Successive Partial-Symmetric Rank-One algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors

引用

Journal of the Operations Research Society of China 2019年第1期7卷 147-167页

作者： Tao-Ran Fu Jin-Yan Fan School of Mathematical Sciences Shanghai Jiao Tong UniversityShanghai 200240China School of Mathematical Sciences and MOE-LSCShanghai Jiao Tong UniversityShanghai 200240China

In this paper,we introduce the almost unitarily decomposable conjugate partial-symmetric tensors,which are different from the commonly studied orthogonally decomposable tensors by involving the conjugate terms in the decomposition and the perturbation *** not only show that successive rank-one approximation algorithm exactly recovers the unitary decomposition of the unitarily decomposable conjugate partial-symmetric *** perturbation analysis of successive rank-one approximation algorithm for almost unitarily decomposable conjugate partial-symmetric tensors is also provided to demonstrate the robustness of the algorithm.

关键词： approximation algorithm Complex tensor Perturbation analysis

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time approximation algorithms for the coloring problem in some cases

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期33卷 809-813页

作者： Malyshev, D. S. Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia

We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.

关键词： Coloring problem Computational complexity approximation algorithm Performance guarantee

来源：评论

学校读者我要写书评

暂无评论

The Parallel Seeding algorithm for k-Means Problem with Penalties

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2020年第4期37卷

作者： Li, Min Xu, Dachuan Yue, Jun Zhang, Dongmei Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition a data point set into k clusters such that the sum of the squared distance from each point to its nearest center is minimized. The k-means problem with penalties, denoted by k-MPWP, generalizing the k-means problem, allows that some points can be paid some penalties instead of being clustered. In this paper, we study the seeding algorithm of k-MPWP and propose a parallel seeding algorithm for k-MPWP along with the corresponding theoretical analysis.

关键词： approximation algorithm k-means penalty seeding algorithm parallel

来源：评论

学校读者我要写书评

暂无评论

SCALABLE algorithmS FOR THE SPARSE RIDGE REGRESSION

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第4期30卷 3359-3386页

作者： Xie, Weijun Deng, Xinwei Virginia Tech Dept Ind & Syst Engn Blacksburg VA 24061 USA Virginia Tech Dept Stat Blacksburg VA 24061 USA

Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L-0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of the MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose integrating the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones.

关键词： approximation algorithm chance constraint conic program mixed integer ridge regression

来源：评论

学校读者我要写书评

暂无评论

BETTER GUARANTEES FOR k-MEANS AND EUCLIDEAN k-MEDIAN BY PRIMAL-DUAL algorithmS

引用

SIAM JOURNAL ON COMPUTING 2020年第4期49卷 FOCS17-97-FOCS17-156页

作者： Ahmadian, Sara Norouzi-Fard, Ashkan Svensson, Ola Ward, Justin Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+epsilon, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard linear programming (LP) relaxation. Our techniques are quite general, and we also show improved guarantees for k-median in Euclidean metrics and for a generalization of k-means in which the underlying metric is not required to be Euclidean.

关键词： k-means approximation algorithm primal-dual k-median LP-based algorithm clustering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：