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

5th International Conference on algorithms for Computational Biology (AlCoB)

作者： Alexandrino, Alexsandro Oliveira Lintzmayer, Carla Negri Dias, Zanoni Univ Estadual Campinas UNICAMP Inst Comp Av Albert Einstein 1251 Campinas SP Brazil Fed Univ ABC UFABC Ctr Math Computat & Cognit Av Estados 5001 Santo Andre Brazil

ISBN: (纸本)9783319919386;9783319919379

Rearrangements are mutations that affect large portions of a genome. When comparing two genomes, one wants to find a sequence of rearrangements that transforms one into another. When we use permutations to represent the genomes, this reduces to the problem of sorting a permutation using some sequence of rearrangements. The traditional approach is to find a sequence of minimum length. However, some studies show that some rearrangements are more likely to disturb an individual, and so a weighted approach is closer to the real evolutionary process. Most weighted approaches consider that the cost of a rearrangement can be related to its type or to the number of elements affected by it. This work introduces a new type of cost function, which is related to the amount of fragmentation caused by a rearrangement. We present some results about lower and upper bounds for the fragmentation-weighted problems and the relation between the unweighted and the fragmentation-weighted approach. Our main results are 2-approximation algorithms for 5 versions of the fragmentation-weighted problem involving reversals and transpositions events.

关键词： Genome rearrangements Sorting permutations approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

p-Edge/Vertex-Connected Vertex Cover: Parameterized and approximation algorithms

arXiv

引用

arXiv 2020年

作者： Einarson, Carl Gutin, Gregory Jansen, Bart M.P. Majumdar, Diptapriyo Wahlström, Magnus Royal Holloway University of London Egham United Kingdom Eindhoven University of Technology Netherlands Indraprastha Institute of Information Technology Delhi New Delhi India

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p ≥ 2 is a fixed integer). We obtain an 2O(pk)nO(1)-time algorithm for p-Edge-Connected VC and an 2O(k2)nO(1)-time algorithm for p-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP ⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2(p + 1)-approximation algorithm for the p-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p-vertex/edge-connected subgraphs of a p-vertex/edge-connected graph by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992). Copyright © 2020, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for a Two-Phase Knapsack Problem 1

引用

24th International Computing and Combinatorics Conference (COCOON)

作者： Nip, Kameng Wang, Zhenbo Sun Yat Sen Univ Sch Math Zhuhai Zhuhai Peoples R China Tsinghua Univ Dept Math Sci Beijing Peoples R China

ISBN: (数字)9783319947761

ISBN: (纸本)9783319947761;9783319947754

We consider a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes, and a large knapsack called container. Each item has a size and profit, each box has a size and the container has a capacity. The first phase is to select some items to pack into the boxes, and the second phase is to select the boxes (each includes some packed items) to pack into the container. The total profit of the problem is determined by the items that are selected and packed into the container within some packed box, and the objective is to maximize the total profit. This problem is motivated by various practical applications, e.g., in logistics. It is a generalization of the multiple knapsack problem, and hence is strongly NP-hard. We mainly propose three approximation algorithms for it. Particularly, the first one is a 1/4-approximation algorithm based on its linear programming relaxation;the second one is based on applying the algorithms for the multiple knapsack problem and the knapsack problem, and has an approximation ratio 1/3- epsilon for any small enough epsilon > 0. We finally provide a polynomial time approximation scheme for this problem.

关键词： Knapsack Multiple knapsack approximation algorithms Polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Cascading Prediction Models 35

Approximation Algorithms for Cascading Prediction Models

引用

35th International Conference on Machine Learning (ICML)

作者： Streeter, Matthew Google Res Mountain View CA 94043 USA

ISBN: (纸本)9781510867963

We present an approximation algorithm that takes a pool of pre-trained models as input and produces from it a cascaded model with similar accuracy but lower average-case cost. Applied to state-of-the-art ImageNet classification models, this yields up to a 2x reduction in floating point multiplications, and up to a 6x reduction in average-case memory I/O. The auto-generated cascades exhibit intuitive properties, such as using lower-resolution input for easier images and requiring higher prediction confidence when using a computationally cheaper model.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for LCS and LIS with Truly Improved Running Times

Approximation Algorithms for LCS and LIS with Truly Improved...

引用

Annual IEEE Symposium on Foundations of Computer Science

作者： Aviad Rubinstein Saeed Seddighin Zhao Song Xiaorui Sun Computer Science Department Stanford University Stanford California USA SEAS Harvard University Cambridge Massachusetts USA Simons Institute for the Theory of Computing Berkeley California USA Computer Science Department University of Illinois at Chicago Chicago Illinois USA

Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent evidence suggests that solving the problem may be impossible in truly subquadratic time. A special case of LCS wherein each character appears at most once in every string is equivalent to the longest increasing subsequence problem (LIS) which can be solved in quasilinear time. In this work, we present novel algorithms for approximating LCS in truly subquadratic time and LIS in truly sublinear time. Our approximation factors depend on the ratio of the optimal solution size over the input size. We denote this ratio by λ and obtain the following results for LCS and LIS without any prior knowledge of λ. A truly subquadratic time algorithm for LCS with approximation factor O(λ 3 ). A truly sublinear time algorithm for LIS with approximation factor O(λ 3 ). Triangle inequality was recently used by Boroujeni et al. [1] and Chakraborty et al.[2] to present new approximation algorithms for edit distance. Our techniques for LCS extend the notion of triangle inequality to non-metric settings.

关键词： approximation algorithms Computer science Complexity theory Additives Sun Optimization Transforms

来源：评论

学校读者我要写书评

暂无评论

Strategy-proof approximation algorithms for the stable marriage problem with ties and incomplete lists 30

Strategy-proof approximation algorithms for the stable marri...

引用

30th International Symposium on algorithms and Computation, ISAAC 2019

作者： Hamada, Koki Miyazaki, Shuichi Yanagisawa, Hiroki NTT Corporation 3-9-11 Midori-cho Musashino-shi Tokyo180-8585 Japan Graduate School of Informatics Kyoto University Yoshida-Honmachi Sakyo-ku Kyoto606-8501 Japan Academic Center for Computing and Media Studies Kyoto University Yoshida-Honmachi Sakyo-ku Kyoto606-8501 Japan IBM Research - Tokyo 19-21 Hakozaki-cho Nihombashi Chuoh-ku Tokyo103-8510 Japan

ISBN: (纸本)9783959771306

In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that it is strategy-proof to the men's side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof mechanism. (Of course, if we flip the roles of men and women, we can see that the woman-oriented Gale-Shapley algorithm (WGS) is a woman-strategy-proof but not a man-strategy-proof mechanism.) Roth has shown that there is no stable mechanism that is simultaneously man-strategy-proof and woman-strategy-proof, which is known as Roth's impossibility theorem. In this paper, we extend these results to the stable marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth's impossibility theorem takes over to SMTI. Therefore, we focus on the one-sided-strategy-proofness. In SMTI, one instance can have stable matchings of different sizes, and it is natural to consider the problem of finding a largest stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratios used in the theory of approximation algorithms. We say that a stable-mechanism is a c-approximate-stable mechanism if it always returns a stable matching of size at least 1/c of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men's lists can contain ties (and women's lists must be strictly ordered). Our results are summarized as follows: (i) MAX SMTI admits both a man-strategy-proof 2-approximate-stable mechanism and a woman-strategy-proof 2-approximate-stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof 2-approximate-stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof 1.5-approximate-stable mechanism. All these results are

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Replenishment Problems with Fixed Turnover Times 1

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Bosman, Thomas van Ee, Martijn Jiao, Yang Marchetti-Spaccamela, Alberto Ravi, R. Stougie, Leen Vrije Univ Amsterdam Netherlands Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA Sapienza Univ Rome Rome Italy CWI Amsterdam Netherlands INRIA Erable Paris France Netherlands Def Acad Den Helder Netherlands

ISBN: (数字)9783319774046

ISBN: (纸本)9783319774046;9783319774039

We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Nodes with capacity for storing a certain commodity are located at various places;at each node the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Nodes should never run empty, and to prevent this we may schedule nodes for replenishment every day. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a node becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each store and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min-avg minimizes the average tour length and min-max minimizes the maximum tour length over all days. For min-max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min-avg we present a logarithmic approximation on general metrics, 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Almost optimal classical approximation algorithms for a quantum generalization of max-cut 22

Almost optimal classical approximation algorithms for a quan...

引用

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

作者： Gharibian, Sevag Parekh, Ojas University of Paderborn Germany Virginia Commonwealth University RichmondVA United States Sandia National Laboratories AlbuquerqueNM United States

ISBN: (纸本)9783959771252

approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal;we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively. © Sevag Gharibian and Ojas Parekh.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Adaptive Target Profit Maximization

Efficient Approximation Algorithms for Adaptive Target Profi...

引用

International Conference on Data Engineering

作者： Keke Huang Jing Tang Xiaokui Xiao Aixin Sun Andrew Lim School of Comp. Sci. and Engg. Nanyang Technological University Dept. of Ind. Syst. Engg. and Mgmt. National University of Singapore School of Computing National University of Singapore

ISBN: (数字)9781728129037

ISBN: (纸本)9781728129044

Given a social network G, the profit maximization (PM) problem asks for a set of seed nodes to maximize the profit, i.e., revenue of influence spread less the cost of seed selection. The target profit maximization (TPM) problem, which generalizes the PM problem, aims to select a subset of seed nodes from a target user set T to maximize the profit. Existing algorithms for PM mostly consider the nonadaptive setting, where all seed nodes are selected in one batch without any knowledge on how they may influence other users. In this paper, we study TPM in adaptive setting, where the seed users are selected through multiple batches, such that the selection of a batch exploits the knowledge of actual influence in the previous batches. To acquire an overall understanding, we study the adaptive TPM problem under both the oracle model and the noise model, and propose ADG and AddATP algorithms to address them with strong theoretical guarantees, respectively. In addition, to better handle the sampling errors under the noise model, we propose the idea of hybrid error based on which we design a novel algorithm HATP that boosts the efficiency of AddATP significantly. We conduct extensive experiments on real social networks to evaluate the performance, and the experimental results strongly confirm the superiorities and effectiveness of our solutions.

关键词： Adaptation models Social network services approximation algorithms Integrated circuit modeling Probabilistic logic Additives

来源：评论

学校读者我要写书评

暂无评论

Conditionally optimal approximation algorithms for the girth of a directed graph

arXiv

引用

arXiv 2020年

作者： Dalirrooyfard, Mina Williams, Virginia Vassilevska

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. Copyright © 2020, The Author

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：