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

International Congress of Mathematicians (ICM)

作者： Williams, Ryan Stanford Univ Dept Comp Sci Stanford CA 94305 USA

ISBN: (纸本)9788961058070

The title of this paper highlights an emerging duality between two basic topics in algorithms and complexity theory. algorithms for circuits refers to the design of algorithms which can analyze finite logical circuits or Boolean functions as input, checking a simple property about the complexity of the underlying function. For instance, an algorithm determining if a given logical circuit C has an input that makes C output true would solve the NP-complete Circuit-SAT problem. Such an algorithm is unlikely to run in polynomial time, but could possibly be more efficient than exhaustively trying all possible inputs to the circuit. Circuits for algorithms refers to the modeling of "complex" uniform algorithms with "simple" Boolean circuit families, or proving that such modeling is impossible. For example, can every exponential-time algorithm be simulated using Boolean circuit families of only polynomial size? It is widely conjectured that the answer is no, but the present mathematical tools available are still too crude to resolve this kind of separation problem. This paper surveys these two generic subjects and the connections that have been developed between them, focusing on connections between non-trivial circuit-analysis algorithms and proofs of circuit complexity lower bounds.

关键词： circuit complexity algorithm analysis satisfiability lower bounds derandomization learning exact algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for Circuits and Circuits for algorithms

Algorithms for Circuits and Circuits for Algorithms

引用

IEEE 29th Conference on Computational Complexity (CCC)

作者： Williams, Ryan Stanford Univ Dept Comp Sci Stanford CA 94305 USA

ISBN: (纸本)9781479936267

The title of this paper is meant to highlight an emerging duality between two fundamental topics in algorithms and complexity theory. algorithms for circuits refers to the design of interesting algorithms which can perform non-trivial circuit analysis of some kind, on either a circuit or a Boolean function given as a truth table. For instance, an algorithm determining whether a given circuit has an input that forces a true output would solve the NP-complete Circuit-SAT problem. Such an algorithm is of course unlikely to run in polynomial time, but could possibly be more efficient than exhaustively trying all possible inputs to the circuit. Circuits for algorithms refers to the modeling of uniform algorithms with non-uniform circuit families (or proving such modeling is impossible). For instance, the NEXP versus P/poly question asks whether nondeterministic exponential-time algorithms can be simulated using non-uniform circuit families of polynomial size. It is widely believed that the answer is no, however the present mathematical tools available are still too crude to prove this kind of separation. This paper surveys these two generic subjects, the ways in which they arise, and connections that have been developed between them, focusing on the connections between nontrivial circuit-analysis algorithms and proofs of circuit size lower bounds. To give one example, if there is a nontrivial algorithm (running slightly faster than exhaustive search) that can determine if a given circuit computes a constant function, then it can be concluded that NEXP is not contained in P/poly. Informally, this connection can be interpreted as saying "some good algorithms for circuits imply there are no good circuits for some algorithms."

关键词： satisfiability derandomization exact algorithms learning circuit complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Vehicle Routing Philadelphia :

引用

丛书名： MOS-SIAM Series on Optimization

2014年

作者： Paolo Toth Daniele Vigo

ISBN: (数字)9781611973594

ISBN: (纸本)9781611973587

Vehicle routing problems, among the most studied in combinatorial optimization, arise in many practical contexts (freight distribution and collection, transportation, garbage collection, newspaper delivery, etc.). Operations researchers have made significant developments in the algorithms for their solution, and Vehicle Routing: Problems, Methods, and Applications, Second Edition reflects these advances. The text of the new edition is either completely new or significantly revised and

provides extensive and complete state-of-the-art coverage of vehicle routing by those who have done most of the innovative research in the area;
emphasizes methodology related to specific classes of vehicle routing problems and, since vehicle routing is used as a benchmark for all new solution techniques, contains a complete overview of current solutions to combinatorial optimization problems;
includes several chapters on important and emerging applications, such as disaster relief and green vehicle routing.

关键词： vehicle routing logistics combinatorial optimization heuristic algorithms exact algorithms transportation science

来源：评论

学校读者我要写书评

暂无评论

ITERATIVE SIMULATION AND OPTIMIZATION APPROACH FOR JOB SHOP SCHEDULING

ITERATIVE SIMULATION AND OPTIMIZATION APPROACH FOR JOB SHOP ...

引用

Winter Simulation Conference

作者： Kulkarni, Ketki Venkateswaran, Jayendran Indian Inst Technol Ind Engn & Operat Res Room 308A Mech Engn Bldg Mumbai 400076 Maharashtra India

ISBN: (纸本)9781479974863

In this paper, we present an iterative scheme integrating simulation with an optimization model, for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem which is NP-Hard, has often been modelled as Mixed-Integer Programming (MIP) model and solved using exact algorithms (for example, branch-and-bound and branch-and-cut) or using meta-heuristics (for example, Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing). In the proposed Iterative Simulation-Optimization (ISO)approach, we use a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities are used to introduce feedback constraints, that help exchange information between the two models. The proposed method is tested using benchmark instances from the OR library. The results indicate that the method gives near optimal schedules in a reasonable computational time.

关键词： computational complexity integer programming iterative methods job shop scheduling ISO approach MIP model NP-hard problem controller delay decision variables exact algorithms feedback constraints iterative simulation-optimization approach job shop scheduling problem meta-heuristics mixed-integer programming model queue priority simulation model Analytical models Computational modeling Job shop scheduling Linear programming Mathematical model Optimization Schedules Job shop scheduling Nondeterministic polynomial-time hard Computational modeling ANALYSIS MODELS iterative methods Integer Programming Simulation models linear programming complexity classes Mathematical Model Integer programming models

来源：评论

学校读者我要写书评

暂无评论

A survey on multi-constrained optimal path computation exact and approximate algorithms

引用

COMPUTER NETWORKS 2010年第17期54卷 3081-3107页

作者： Garroppo, Rosario G. Giordano, Stefano Tavanti, Luca Univ Pisa Dip Ingn Informaz I-56122 Pisa Italy

The paper presents a survey on the techniques to solve the multi-constrained optimal path (MCOP) problem Computing the MCOP is a task shared by many research areas from transportation systems to telecommunication networks In the latter the MCOP is often related to the issue of Quality of Service (QoS) routing which consists in finding a route between a couple of nodes that meets a series of QoS requirements such as bounded delay pack et loss and other parameters The MCOP problem has been faced by several authors and a plethora of solving methods is now available In the present work we draw the state of the art of exact and approximate MCOP computation algorithms with particular attention to the networking area We describe and analyse the most representative methods and for each of them we derive the worst case computational complexity In addition we provide the reader with a uniform notation and with the detailed pseudo-code of various algorithms so that the paper can indeed serve as a workable starting point for further studies on the MCOP problem (C) 2010 Elsevier B V All rights reserved

关键词： Multi Constrained Optimal Path (MCOP) Multi Objective Optimal Path (MOOP) Multi Constrained Path (MCP) Restricted Shortest Path (RSP) Quality of Service (QoS) Routing exact algorithms Approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Two Approaches for the Resolution of a Resources System Selection Problem for Distributed/Agile/Virtual Enterprises – A Contribution to the Broker Performance

引用

Procedia Technology 2014年 16卷 906-912页

作者： Paulo Ávila Alzira Mota Lino Costa Goran Putnik João Bastos Manuel Lopes Politechnic of Porto School of Engineering Rua António Bernardino de Almeida 431. 4200-072 Porto Portugal University of Minho Campus de Gualtar 4710-057 Braga Portugal

In the ambit of Distribute/Agile/Virtual Enterprises, the resources/partners selection process is a critical issue in order to guarantee the success of such enterprises. The selection process is complex in the large sense of the word and for that we advocate the necessity of a broker to perform that task, conveniently assisted by a tool. In order to contribute to its construction, this paper presents the resolution of a resources system selection problem, designated by Dependent or Integral Selection Method without Pre-selection of Transport Resources , with two algorithms, an exact solution algorithm and an approximate one. The results demonstrate that the exact solution algorithm limitations can be covered by the approximate algorithm. With those results, the broker has the knowledge to perform the selection with the most adequate algorithm for each case of the problem (depending of the number of tasks and pre-selected resources) addressed in this paper. This paper brings a contribution to broker performance for the selection process.

关键词： Distributed/Agile/Virtual Enterprises Resources System Selection Problem exact algorithms Genetic algorithms Broker Performance.

来源：评论

学校读者我要写书评

暂无评论

Computing Optimal Steiner Trees in Polynomial Space

引用

ALGORITHMICA 2013年第3期65卷 584-604页

作者： Fomin, Fedor V. Grandoni, Fabrizio Kratsch, Dieter Lokshtanov, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Italian Switzerland IDSIA CH-6928 Manno Switzerland Univ Paul Verlaine Metz LITA F-57045 Metz 01 France Inst Math Sci Madras 600113 Tamil Nadu India

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 (n) )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) (k) n (O(logk)))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to . This improves on trivial enumeration for roughly k < n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 (n) )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 (n) )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713-725, 2009), the running time can be reduced to O(1.36 (n) ). The previous

关键词： Steiner tree exact algorithms Space complexity

来源：评论

学校读者我要写书评

暂无评论

Constraints in container loading - A state-of-the-art review

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2013年第1期229卷 1-20页

作者： Bortfeldt, Andreas Waescher, Gerhard Otto Von Guericke Univ Fac Econ & Management Dept Management Sci Magdeburg Germany

Container loading is a pivotal function for operating supply chains efficiently. Underperformance results in unnecessary costs (e.g. cost of additional containers to be shipped) and in an unsatisfactory customer service (e.g. violation of deadlines agreed to or set by clients). Thus, it is not surprising that container loading problems have been dealt with frequently in the operations research literature. It has been claimed though that the proposed approaches are of limited practical value since they do not pay enough attention to constraints encountered in practice. In this paper, a review of the state-of-the-art in the field of container loading will be given. We will identify factors which from a practical point of view need to be considered when dealing with container loading problems and we will analyze whether and how these factors are represented in methods for the solution of such problems. Modeling approaches, as well as exact and heuristic algorithms will be reviewed. This will allow for assessing the practical relevance of the research which has been carried out in the field. We will also mention several issues which have not been dealt with satisfactorily so far and give an outlook on future research opportunities. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Container loading Cutting Packing Constraints exact algorithms Heuristics

来源：评论

学校读者我要写书评

暂无评论

Assembly line balancing under uncertainty: Robust optimization models and exact solution method

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2013年第2期65卷 261-267页

作者： Hazir, Oncu Dolgui, Alexandre TED Univ Iktisadi & Idari Bilimler Fak TR-06420 Ankara Turkey Ecole Natl Super Mines EMSE FAYOL CNRS UMR6158 LIMOS F-42023 St Etienne France

This research deals with line balancing under uncertainty and presents two robust optimization models. Interval uncertainty for operation times was assumed. The methods proposed generate line designs that are protected against this type of disruptions. A decomposition based algorithm was developed and combined with enhancement strategies to solve optimally large scale instances. The efficiency of this algorithm was tested and the experimental results were presented. The theoretical contribution of this paper lies in the novel models proposed and the decomposition based exact algorithm developed. Moreover, it is of practical interest since the production rate of the assembly lines designed with our algorithm will be more reliable as uncertainty is incorporated. Furthermore, this is a pioneering work on robust assembly line balancing and should serve as the basis for a decision support system on this subject. (c) 2013 Elsevier Ltd. All rights reserved.

关键词： Assembly line balancing Uncertainty Robust optimization Combinatorial optimization exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Collusion in Atomic Splittable Routing Games

引用

THEORY OF COMPUTING SYSTEMS 2013年第4期52卷 763-801页

作者： Huang, Chien-Chung Humboldt Univ D-10099 Berlin Germany

We study how collusion affects the social cost in atomic splittable routing games. Suppose that players form coalitions and each coalition behaves as if it were a single player controlling all the flows of its participants. We investigate the following question: under what conditions would the social cost of the post-collusion equilibrium be bounded by the social cost of the pre-collusion equilibrium? We show that if (i) the network is "well-designed" (satisfying a natural condition), and (ii) the delay functions are affine, then collusion is always beneficial for the social cost in the equilibrium flows. On the other hand, if either of the above conditions is unsatisfied, collusion can worsen the social cost. Our main technique is a novel flow-augmenting algorithm to build equilibrium flows. Our positive result for collusion is obtained by applying this algorithm simultaneously to two different flow value profiles of players and observing the difference in the derivatives of their social costs. Moreover, for a non-trivial subclass of selfish routing games, this algorithm finds the exact equilibrium flows in polynomial time.

关键词： Selfish routing Collusion Social cost Nash equilibria exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：