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

Graph Isomorphism, Color Refinement, and Compactness

COMPUTATIONAL COMPLEXITY 2017年第3期26卷 627-685页

作者： Arvind, V. Koebler, Johannes Rattan, Gaurav Verbitsky, Oleg Inst Math Sci Chennai 600113 Tamil Nadu India Humboldt Univ Inst Informat Unter Linden 6 D-10099 Berlin Germany

Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic;it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if the color refinement procedure succeeds in distinguishing G from any non-isomorphic graph H. Babai et al. (SIAM J Comput 9(3):628-635, 1980) have shown that random graphs are amenable with high probability. We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time , where n and m denote the number of vertices and the number of edges in the input graph. We use our characterization of amenable graphs to analyze the approach to Graph Isomorphism based on the notion of compact graphs. A graph is called compact if the polytope of its fractional automorphisms is integral. Tinhofer (Discrete Appl Math 30(2-3):253-264, 1991) noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing compact graphs and recognizing them in polynomial time remains an open question. Our results in this direction are summarized below: We show that all amenable graphs are compact. In other words, the applicability range for Tinhofer's linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement. Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy, and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.

关键词： Graph Isomorphism color refinement linear programming relaxation polytope of fractional automorphisms

来源：评论

学校读者我要写书评

暂无评论

The solution of two-stage guillotine cutting stock problems having extremely varying order demands

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1996年第3期91卷 543-552页

作者： Riehme, J Scheithauer, G Terno, J DRESDEN UNIV TECHNOL INST NUMER MATHD-01069 DRESDENGERMANY

In this paper the solution of two-stage guillotine cutting stock problems is considered. Especially such problems are under investigation where the sizes of the order demands differ in a large range. We propose a new approach dealing with such situations and compare it with the classical Gilmore-Gomory approach. We report results of extensive numerical experiments which show the advantages of the new approach.

关键词： cutting stock problem two-stage guillotine cutting linear programming relaxation column generation

来源：评论

学校读者我要写书评

暂无评论

PROBABILISTIC ANALYSIS OF THE HELD AND KARP LOWER BOUND FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM

引用

MATHEMATICS OF OPERATIONS RESEARCH 1991年第1期16卷 72-89页

作者： GOEMANS, MX BERTSIMAS, DJ MIT ALFRED P SLOAN SCH MANAGEMENTCAMBRIDGEMA 02139

We analyze probabilistically the classical Held-Karp lower bound derived from the 1-tree relaxation for the Euclidean traveling salesman problem (ETSP). We prove that, if n points are identically and independently distributed according to a distribution with bounded support and absolutely continuous part f(x) dx over the d-cube, the Held-Karp lower bound on these n points is almost surely asymptotic to beta-HK(d)n(d-1)/d integral f(x)(d-1)/d dx, where beta-HK(d) is a constant independent of n. The result suggests a probabilistic explanation of the observation that the lower bound is very close to the length of the optimal tour in practice, since the ETSP is almost surely asymptotic to beta-TSP(d)n(d-1)/d integral f(x)(d-1)/d dx. The techniques we use exploit the polyhedral description of the Held-Karp lower bound and the theory of subadditive Euclidean functionals.

关键词： PROBABILISTIC ANALYSIS TRAVELING SALESMAN PROBLEM linear programming relaxation 1-TREES SUBADDITIVE EUCLIDEAN FUNCTIONALS

来源：评论

学校读者我要写书评

暂无评论

Minimizing the Stabbing Number of Matchings, Trees, and Triangulations

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2008年第4期40卷 595-621页

作者： Fekete, Sandor P. Luebbecke, Marco E. Meijer, Henk Tech Univ Carolo Wilhelmina Braunschweig Dept Comp Sci Algorithms Grp D-38106 Braunschweig Germany Tech Univ Berlin Inst Math D-10623 Berlin Germany Roosevelt Acad Dept Sci Middelburg ZL Netherlands

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of vertices. The complexity of finding a spanning tree of minimum stabbing number is one of the original 30 questions on "The Open Problems Project" list of outstanding problems in computational geometry by Demaine, Mitchell, and O'Rourke. We show NP-hardness of stabbing problems by means of a general proof technique. For matchings, this also implies a nontrivial lower bound on the approximability. On the positive side, we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. From the corresponding linear programming relaxation we obtain polynomial-time lower bounds and show that there always is an optimal fractional solution that contains an edge of at least constant weight. We conjecture that the resulting iterated rounding scheme constitutes a constant-factor approximation algorithm.

关键词： Stabbing number Matching Spanning tree Triangulation Complexity linear programming relaxation Iterated rounding

来源：评论

学校读者我要写书评

暂无评论

Relating domination, exponential domination, and porous exponential domination

引用

DISCRETE OPTIMIZATION 2017年 23卷 81-92页

作者： Henning, Michael A. Jaeger, Simon Rautenbach, Dieter Univ Johannesburg Dept Pure & Appl Math ZA-2006 Auckland Pk South Africa Univ Ulm Inst Optimizat & Operat Res Ulm Germany

The domination number gamma(G) of a graph G, its exponential domination number gamma e (G), and its porous exponential domination number gamma(*)(e)(G) satisfy gamma(e)*(G) <= gamma(e)(G) <= gamma(G). We contribute results about the gaps in these inequalities as well as the graphs for which some of the inequalities hold with equality. Relaxing the natural integer linear program whose optimum value is gamma(e)*(G), we are led to the definition of the fractional porous exponential domination number gamma e* f (G) of a graph G. For a subcubic tree T of order n, we show gamma(e,f)*(T) = n+2/6 and gamma e (T) <= 2 gamma(e,f)*(T). We characterize the two classes of subcubic trees T with gamma(e) (T) =gamma(e,f)* (T) and gamma(T) = gamma(e)(T), respectively. Using linear programming arguments, we establish several lower bounds on the fractional porous exponential domination number in more general settings. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Domination Exponential domination Porous exponential domination linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

A TECHNIQUE FOR SPEEDING-UP THE SOLUTION OF THE LAGRANGEAN DUAL

引用

MATHEMATICAL programming 1994年第1期63卷 23-45页

作者： BERTSIMAS, D ORLIN, JB MIT ALFRED P SLOAN SCH MANAGEMENTE53-35950 MEM DRCAMBRIDGEMA 02139 USA

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, the k-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems, K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.

关键词： LAGRANGEAN relaxation linear programming relaxation POLYNOMIAL ALGORITHM

来源：评论

学校读者我要写书评

暂无评论

EXACT METHODS FOR THE KNAPSACK-PROBLEM AND ITS GENERALIZATIONS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1987年第1期28卷 3-21页

作者： DUDZINSKI, K WALUKIEWICZ, S POLISH ACAD SCI SYST RES INSTUL NEWELSKA 6PL-01447 WARSAWPOLAND

A unified approach and a summary of the most important results concerned with exact methods for solving the (binary) knapsack problem and its generalizations are given. We stress the importance of dual methods for solving linear programming relaxations of the considered problems. Two ways of generalization of the knapsack problem are described. If the special ordered sets are added, then the multiple-choice knapsack problem is obtained. If the constraints have the nested structure, then we get the nested knapsack problem. Also the multiple-choice nested knapsack problem is discussed. [ABSTRACT FROM AUTHOR]

关键词： branch-and-bound Integer programming Lagrangean relaxation linear programming relaxation reduction

来源：评论

学校读者我要写书评

暂无评论

A CLASS OF GENERALIZED GREEDY ALGORITHMS FOR THE MULTI-KNAPSACK PROBLEM

引用

DISCRETE APPLIED MATHEMATICS 1993年第2-3期42卷 279-290页

作者： KAN, AHGR STOUGIE, L VERCELLIS, C POLITECN MILAN DIPARTIMENTO ECON & PRODPIAZZA LEONARDO DA VINCI 32I-20133 MILANITALY ERASMUS UNIV INST ECONOMETR3000 DR ROTTERDAMNETHERLANDS UNIV AMSTERDAM INST ACTUARIAAT & ECONAMSTERDAMNETHERLANDS

A class of generalized greedy algorithms is proposed for the solution of the {0, 1} multi-knapsack problem. Items are selected according to decreasing ratios of their profit and a weighted sum of their requirement coefficients. The solution obtained depends on the choice of the weights. A geometrical representation of the method is given and the relation to the dual of the linear programming relaxation of multi-knapsack is exploited. We investigate the complexity of computing a set of weights that gives the maximum greedy solution value. Finally, the heuristics are subjected to both a worst-case and a probabilistic performance analysis.

关键词： MULTI-KNAPSACK PROBLEM GREEDY HEURISTIC linear programming relaxation COMPUTATIONAL COMPLEXITY WORST-CASE ANALYSIS PROBABILISTIC ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

A cross-monotonic cost sharing method for the facility location game with service installation costs

引用

Science China Mathematics 2009年第11期52卷 2530-2536页

作者： XU DaChuan Department of Applied Mathematics,Beijing University of Technology,Beijing 100124,China 1. Department of Applied Mathematics Beijing University of Technology Beijing 100124 China

In this paper,we consider the metric uncapacitated facility location game with service installation costs. Our main result is an 11-approximate cross-monotonic cost-sharing method under the assumption that the install... 详细信息

关键词： facility location game cross-monotonic cost-sharing method linear programming relaxation 90C27 91A12

来源：评论

学校读者我要写书评

暂无评论

Load Balanced Mobile User Recruitment for Mobile Crowdsensing Systems

引用

IEEE COMMUNICATIONS LETTERS 2017年第11期21卷 2420-2423页

作者： An, Xin Guo, Hao Wang, Xiumin Chen, Xiaoming Hefei Univ Technol Sch Comp & Informat Hefei 230009 Anhui Peoples R China South China Univ Technol Sch Comp Sci & Engn Guangzhou 510006 Guangdong Peoples R China Zhejiang Univ Coll Informat Sci & Elect Engn Hangzhou 310058 Zhejiang Peoples R China

In this letter, we study the mobile user recruitment problem for mobile crowdsensing systems. Instead of minimizing the overall sensing cost or user utility, this letter aims to optimize the load balancing of the mobile users, which is particularly important for the resource-constrained individual user. We refer to such a problem as the load balanced mobile user recruitment (LB-MUR) problem. Specifically, we first formulate the LB-MUR problem as a mixed integer linear programming (LP) and prove that it is NP-hard. Then an efficient polynomial-time suboptimal algorithm is proposed, which is based on LP relaxation. Furthermore, we derive the approximation ratio of the proposed algorithm. Finally, we evaluate the effectiveness of the proposed scheme through simulations.

关键词： Mobile crowdsensing load balance linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：