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

APPROXIMATING THE MINIMUM EQUIVALENT DIGRAPH

SIAM JOURNAL ON COMPUTING 1995年第4期24卷 859-872页

作者： KHULLER, S RAGHAVACHARI, B YOUNG, N UNIV MARYLAND INST ADV COMP STUDIES COLLEGE PK MD 20742 USA UNIV TEXAS DEPT COMP SCI RICHARDSON TX 75083 USA AT&T BELL LABS MURRAY HILL NJ 07974 USA

The minimum equivalent graph (MEG) problem is as follows: given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes. This problem is NP-hard;this paper gives an approximation algorithm achieving a performance guarantee of about 1.64 in polynomial time. The algorithm achieves a performance guarantee of 1.75 in the time required for transitive closure. The heart of the MEG problem is the minimum strongly connected spanning subgraph (SCSS) problem-the MEG problem restricted to strongly connected digraphs. For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1.75. The algorithm and its analysis are based on the simple idea of contracting long cycles. The analysis applies directly to 2-EXCHANGE, a general ''local improvement'' algorithm, showing that its performance guarantee is 1.75.

关键词： DIRECTED GRAPH approximation algorithm STRONG CONNECTIVITY LOCAL IMPROVEMENT

来源：评论

学校读者我要写书评

暂无评论

A PTAS for single machine scheduling with controllable processing times

引用

Acta Cybernetica 2002年第3期15卷 369-378页

作者： Schuurman, Petra Woeginger, Gerhard J. Department of Mathematics and Computing Science Eindhoven University of Technology P.O. Box 513 5600 MB Eindhoven Netherlands Institut für Mathematik B TU Graz Steyrergasse 30 A-8010 Graz Austria Department of Mathematics University of Twente 7500 AE Enschede Netherlands

We deal with a single machine scheduling problem in which each job has a release date, a delivery time and a controllable processing time. The fact that the jobs have a controllable processing time means that it is allowed to compress (a part of) the processing time of the job, in return for compression cost. The objective is to find a schedule that minimizes the total cost, that is, the latest delivery time of any job plus the total compression cost. In this note we discuss how the techniques of Hall and Shmoys [3] and Hall [1] can directly be applied to design a polynomial time approximation scheme for this problem.

关键词： approximation algorithm approximation scheme Controllable processing time Scheduling Worst case analysis

来源：评论

学校读者我要写书评

暂无评论

Minimum nonuniform graph partitioning with unrelated weights

引用

SBORNIK MATHEMATICS 2017年第12期208卷 1835-1853页

作者： Makarychev, K. S. Makarychev, Yu. S. Northwestern Univ Evanston IL 60208 USA Toyota Technol Inst Chicago Chicago IL USA

We give a bi-criteria approximation algorithm for the Minimum Nonuniform Graph Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz and Talwar. In this problem, we are given a graph G = (V, E) and k numbers rho(1),..., rho(k). The goal is to partition V into k disjoint sets (bins) P-1,..., P-k satisfying vertical bar P-i vertical bar <= rho(i)vertical bar V vertical bar for all i, so as to minimize the number of edges cut by the partition. Our bi-criteria algorithm gives an O(root log vertical bar V vertical bar log k) approximation for the objective function in general graphs and an O(1) approximation in graphs excluding a fixed minor. The approximate solution satisfies the relaxed capacity constraints vertical bar P-i vertical bar <= (5 + epsilon)rho(i)vertical bar V vertical bar. This algorithm is an improvement upon the O(log vertical bar V vertical bar)-approximation algorithm by Krauthgamer, Naor, Schwartz and Talwar. We extend our results to the case of 'unrelated weights' and to the case of 'unrelated d-dimensional weights'. A preliminary version of this work was presented at the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014).

关键词： minimum nonuniform graph partitioning problem minimum nonuniform graph partitioning problem with unrelated weights approximation for trees approximation algorithm semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

New bounds on the anti-Ramsey numbers of star graphs via maximum edge q-coloring

引用

DISCRETE MATHEMATICS 2024年第4期347卷

作者： Chandran, L. Sunil Hashim, Talha Jacob, Dalu Mathew, Rogers Rajendraprasad, Deepak Singh, Nitin Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 India Indian Inst Technol Dept Comp Sci & Engn Hyderabad 502285 India Indian Inst Technol Dept Comp Sci & Engn Palakkad 678557 India IBM Res Lab Manyata Embassy Business Pk Bangalore 560045 India Univ Haifa Haifa Israel Max Planck Inst Informat Saarbrucken Germany

The anti -Ramsey number ar(G, H) with input graph G and pattern graph H, is the maximum positive integer k such that there exists an edge coloring of G using k colors, in which there are no rainbow subgraphs isomorphic to H in G. (H is rainbow if all its edges get distinct colors). The concept of anti -Ramsey number was introduced by Erdos et al. in 1973. Thereafter, several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti -Ramsey problem for the pattern graph K-1,K-t (for t >= 3) purely from an algorithmic point of view. For a graph G and an integer q >= 2, an edge q -coloring of G is an assignment of colors to edges of G, such that the edges incident on a vertex span at most q distinct colors. The maximum edge q -coloring problem seeks to maximize the number of colors in an edge q -coloring of the graph G. Note that the optimum value of the edge q -coloring problem of G equals ar(G, K-1,K-q+1). Here, we study ar(G, K-1,K-t), the anti -Ramsey number of stars, for each fixed integer t >= 3, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for ar(G, K-1,K-q+1), in terms of number of vertices and the minimum degree of G. The second one improves this result for the case of triangle -free input graphs. Our third main result presents an upper bound for ar(G, K-1,K-q+1) in terms of |E(G(<=(q-1)))|, which is a frequently used lower bound for ar(G, K-1,K-q+1) and maximum edge q -coloring in the literature. All our results have algorithmic consequences. (c) 2024 Elsevier B.V. All rights reserved.

关键词： Anti -Ramsey number Maximum edge q -coloring problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING

引用

PARALLEL PROCESSING LETTERS 2012年第2期22卷 1250006-1250006页

作者： Ooshita, Fukuhito Izumi, Tomoko Izumi, Taisuke Osaka Univ Grad Sch Informat Sci & Technol 1-5 Yamadoka Suita Osaka 5650871 Japan Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu Shiga 5258577 Japan Nagoya Inst Technol Grad Sch Engn Syowa Ku Nagoya Aichi 4668555 Japan

We consider the parallel computing environment where m organizations provide machines and several jobs to be executed. While cooperation of organizations is required to minimize the global makespan, each organization also expects the faster completion of its own jobs primarily and thus it is not necessarily cooperative. To handle the situations, we formulate the a-cooperative multi-organization scheduling problem (alpha-MOSP), where alpha >= 1 is a parameter representing the degree of cooperativeness. alpha-MOSP minimizes the makespan under the multi-organization constraint that each organization does not allow the completion time of its own jobs to be delayed a times of that in the case where those jobs are executed by itself. First, we reveal the relation between the makespan and the degree of cooperativeness. We show that the multi-organization constraint may degrade the optimal makespan by m times for a = 1, while the degradation ratio is bounded by alpha/(alpha- 1) for a > 1. This implies that weak cooperation improves the makespan dramatically. Second, we study the complexity of a-MOSP. We show its strongly NP-hardness and inapproximability for the approximation factor less than max{(alpha + 1)/alpha, 3/2}. We also show the hardness of transformation from an optimal schedule under no multi-organization constraint to an optimal schedule for a-MOSP. This result is a witness for inexistence of a general polynomial-time transformation algorithm that preserves the approximation ratio.

关键词： Heterogeneous parallel computing environments scheduling algorithm multi-organization scheduling approximation algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

-Free Graphs are 4-Colorable: 收藏
分享
引用; SIAM Journal on Discrete Mathematics 2019年第2期33卷 1095-1120页; 作者： Serge Gaspers Shenwei Huang; In this paper, we show that every (2P2,<span class="msubsup" id="MathJax-Span-21" style="paddi; In this paper, we show that every $(2 P_{2}, K_{4})$; 来源：评论; 学校读者我要写书评

暂无评论

Joint User Pairing and Resource Allocation for Virtual MIMO in uplink SC-FDMA System

Joint User Pairing and Resource Allocation for Virtual MIMO ...

引用

International Conference on Wireless Communications and Signal Processing (WCSP)

作者： Wu, Chunliang Chen, Li Wei, Guo Univ Sci & Technol China Dept Elect Engn & Informat Sci Hefei 230027 Peoples R China

ISBN: (纸本)9781479903085

In this paper, we study the joint user pairing and resource allocation problem for uplink single carrier frequency-division multiple access (SC-FDMA) system with virtual multiple-input multiple-output (V-MIMO) implemented. Different from existing relevant researches, we consider a universal solution based on profit function for this problem instead of studying a particular scheduling policy, and then we explain that it is a MAX SNP-hard problem with high complexity. After that, we will propose a low-complexity heuristic algorithm called First User First (FuF), which is based on the idea of allocating resource to one user first. Moreover, in order to get a more accurate theoretical approximation to this problem, we will propose a constant factor approximation algorithm with polynomial-time complexity using local ratio technique. The simulation results of our algorithms show that the B-LRT algorithm has robust performance compared with other popular algorithms, while the FuF algorithm has lowest computation complexity at the expense of a little performance loss.

关键词： user pairing resource allocation Virtual MIMO SC-FDMA approximation algorithm profit function

来源：评论

学校读者我要写书评

暂无评论

algorithmS FOR TRIE COMPACTION

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 1984年第2期9卷 243-263页

作者： ALSUWAIYEL, M HOROWITZ, E UNIV SO CALIF DEPT COMP SCILOS ANGELESCA 90089

The trie data structure has many properties which make it especially attractive for representing large files of data. These properties include fast retrieval time, quick unsuccessful search determination, and finding the longest match to a given identifier. The main drawback is the space requirement. In this paper the concept of trie compaction is formalized. An exact algorithm for optimal trie compaction and three algorithms for approximate trie compaction are given, and an analysis of the three algorithms is done. The analysis indicate that for actual tries, reductions of around 70 percent in the space required by the uncompacted trie can be expected. The quality of the compaction is shown to be insensitive to the number of nodes, while a more relevant parameter is the alphabet size of the key.

关键词： approximation algorithm data structure node compaction storage retrieval Trie

来源：评论

学校读者我要写书评

暂无评论

AN algorithmIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS - WITH APPLICATIONS

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2014年第5期25卷 623-639页

作者： Ghasemi, Taha Ghasemalizadeh, Hossein Razzazi, Mohammadreza Amirkabir Univ Technol Software Syst R&D Lab Comp Engn & IT Dept Tehran Iran Inst Res Fundamental Sci IPM Tehran Iran

In geometric covering problems, the aim is to cover a set of given points using a minimum number of shapes with prescribed properties. These problems extend in many ways such as covering in the presence of obstacles and partial covering. Since in most cases these problems are NP-hard, researchers have developed a large number of approximation algorithms to solve them. In this paper, with a more general view on these approadies, we propose an algorithmic framework that gives an approximation algorithm for the covering problem at hand, provided that its prerequisites are satisfied. As the result, we present a general class of geometric covering problems for which one can obtain polynomial-time approximation schemes (PTASs). This class of problems involves covering point sets with bounded shapes in a space with fixed dimension. For a problem to be in this class, it must be possible to find a polynomial number of maximal shapes and it must be possible to cover all the points in a small box with a small number of shapes. Using this frame:work, is e present two new PTASs for the problems covering with disks in the presence of polygonal obstacles and covering with sectors (pie-shaped wedges). The first problem has never been addressed before and for the second problem, only a logarithmic approximation algorithm was known in general and a 9-approximation algorithm for Wide angles.

关键词： Geometric covering covering with disks covering with obstacles covering with sectors set cover problem algorithmic framework approximation algorithm computational gcometry

来源：评论

学校读者我要写书评

暂无评论

Reversals and transpositions distance with proportion restriction

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2021年第4期19卷 2150013-2150013页

作者： Brito, Klairton Lima Alexandrino, Alexsandro Oliveira Oliveira, Andre Rodrigues Dias, Ulisses Dias, Zanoni Univ Estadual Campinas Inst Comp 1251 Albert Einstein Ave BR-13083852 Campinas SP Brazil Univ Estadual Campinas Sch Technol 1888 Paschoal Marmo St BR-13484332 Limeira SP Brazil

In the field of comparative genomics, one way of comparing two genomes is through the analysis of how they distinguish themselves based on a set of mutations called rearrangement events. When considering that genomes undergo different types of rearrangements, it can be assumed that some events are more common than others. To model this assumption, one can assign different weights to different events, where common events tend to cost less than others. However, this approach, called weighted, does not guarantee that the rearrangement assumed to be the most frequent will be also the most frequently returned by proposed algorithms. To overcome this issue, we investigate a new problem where we seek the shortest sequence of rearrangement events able to transform one genome into the other, with a restriction regarding the proportion between the events returned. Here, we consider two rearrangement events: reversal, that inverts the order and the orientation of the genes inside a segment of the genome, and transposition, that moves a segment of the genome to another position. We show the complexity of this problem for any desired proportion considering scenarios where the orientation of the genes is known or unknown. We also develop an approximation algorithm with a constant approximation factor for each scenario and, in particular, we describe an improved (asymptotic) approximation algorithm for the case where the gene orientation is known. At last, we present the experimental tests comparing the proposed algorithms with others from the literature for the version of the problem without the proportion restriction.

关键词： Reversal transposition proportion restriction approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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