%{search_type} search results

This book constitutes the refereed proceedings of the Second International Conference on Combinatorial Optimization and Applications, COCOA 2008, held in St. John's, Canada, in August 2008. The 44 revised full papers were carefully reviewed and selected from 84 submissions. The papers feature original research in the areas of combinatorial optimization - both theoretical issues and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.
(source: Nielsen Book Data)

This book is dedicated to Jack Edmonds in appreciation of his ground breaking work that laid the foundations for a broad variety of subsequent results achieved in combinatorial optimization.The main part consists of 13 revised full papers on current topics in combinatorial optimization, presented at Aussois 2001, the Fifth Aussois Workshop on Combinatorial Optimization, March 5-9, 2001, and dedicated to Jack Edmonds.Additional highlights in this book are an account of an Aussois 2001 special session dedicated to Jack Edmonds including a speech given by William R. Pulleyblank as well as newly typeset versions of three up-to-now hardly accessible classical papers:- Submodular Functions, Matroids, and Certain Polyhedra by Jack Edmonds- Matching: A Well-Solved Class of Integer Linear Programs by Jack Edmonds and Ellis L. Johnson- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems by Jack Edmonds and Richard M. Karp.
(source: Nielsen Book Data)

There have been significant developments in the theory and practice of combinatorial optimization in the last 15 years. Current developments in methodology and applications are presented in the contirbutions to this volume, which contains the proceedings of the NATO Advanced Study Institute held at Bilkent University, Ankara, Turkey, in July 1990. The subject covered in the book include general decomposition in mathematical programming, scheduling problems, network flow problems, and polyhedral combinatorics. Application areas treated include VLSI layout problems, emergency evacuation problems, telecommunication network design, robotic assembly problems, part scheduling, and tool loading problems.
(source: Nielsen Book Data)

• Polyhedra and Algorithms.- New classes of facets for complementarity knapsack problems.- Branch-and-Cut for a 2-Commodity Flow Relocation Model with Time Constraints.- The Constrained-Routing and Spectrum Assignment Problem: Valid Inequalities and Branch-and-Cut Algorithm.- Polyhedra and Combinatorics.- Top-$k$ List Aggregation: Mathematical Formulations and Polyhedral Comparisons.- Bounded variation in binary sequences.- On Minimally Non-Firm Binary Matrices.- Few Induced Disjoint Paths for H-Free Graphs.- On Permuting some Coordinates of Polytopes.- Non-linear Optimization.- Piecewise linearization of bivariate nonlinear functions: minimizing the number of pieces under a bounded approximation error.- An outer-approximation algorithm for maximum-entropy sampling.- Mitigating Anomalies in Parallel Branch-and-Bound Based Algorithms for Mixed-Integer Nonlinear Optimization.- Game Theory.- Exact Price of Anarchy for Weighted Congestion Games with Two Players.- Nash balanced assignment problem.- Graphs and Trees.- On the thinness of trees.- Generating Spanning Tree Sequences of a Fan Graph in Lexicographic Order and Ranking/Unranking Algorithms.- Cutting and Packing.- High Multiplicity Strip Packing with Three Rectangle Types.- Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions.- Applications.- One transfer per patient suffices: Structural insights about patient-to-room assignment.- Tool switching problems in the context of overlay printing with multiple colours.- Optimal Vaccination Strategies for Multiple Dose Vaccinations.- Approximation Algorithms.- Pervasive Domination.- Unified Greedy Approximability Beyond Submodular Maximization.- Neighborhood persistency of the linear optimization relaxation of integer linear optimization.- Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines.
• (source: Nielsen Book Data)

This book constitutes thoroughly refereed and revised selected papers from the 7th International Symposium on Combinatorial Optimization, ISCO 2022, which was held online during May 18-20, 2022. The 24 full papers included in this book were carefully reviewed and selected from 50 submissions. They were organized in topical sections as follows: Polyhedra and algorithms; polyhedra and combinatorics; non-linear optimization; game theory; graphs and trees; cutting and packing; applications; and approximation algorithms.
(source: Nielsen Book Data)

• Algorithms and complexity
• Mathematical programming
• Operations research
• Stochastic optimization
• Graphs and combinatorics.

This book constitutes the thoroughly refereed post-conference proceedings of the Third International Symposium on Combinatorial Optimization, ISCO 2014, held in Lisbon, Portugal, in March 2014. The 37 revised full papers presented together with 64 short papers were carefully reviewed and selected from 97 submissions. They present original research on all aspects of combinatorial optimization, such as algorithms and complexity; mathematical programming; operations research; stochastic optimization; graphs and combinatorics.

• On the Location and p-Median Polytopes.- Facet Generating Techniques.- Antimatroids, Betweenness, Convexity.- Euler Complexes.- Strongly Polynomial Algorithm for the Intersection of a Line with a Polymatroid.- A Survey on Covering Supermodular Functions.- Theory of Principal Partitions Revisited.- Locally Dense Independent Sets in Regular Graphs of Large Girth-An Example of a New Approach.- Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems.- The Unbounded Knapsack Problem.- Recent Developments in Discrete Convex Analysis.- Multiflow Feasibility: An Annotated Tableau.- Many Facets of Dualities.- On the Structure of Graphs Vertex Critical with Respect to Connected Domination.- LS-LIB: A Library of Tools for Solving Production Planning Problems.- From Spheres to Spheropolyhedra: Generalized Distinct Element Methodology and Algorithm Analysis.- Graphic Submodular Function Minimization: A Graphic Approach and Applications.- Matroids-the Engineers' Revenge.- On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming.- Single-Sink Multicommodity Flow with Side Constraints.- An Introduction to Network Flows over Time.- Edge-Connectivity Augmentations of Graphs and Hypergraphs.- Some Problems on Approximate Counting in Graphs and Matroids.
• (source: Nielsen Book Data)

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3-7,2008.Althoughthiswouldbeareasontolookback, wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea, butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these areas.
(source: Nielsen Book Data)

• Machine generated contents note:
• Complexity of Testing Monomials in Multivariate Polynomials / Bin Fu
• Algorithms for Testing Monomials in Multivariate Polynomials / Robert Schweller
• Hybrid Artificial Bee Colony Search Algorithm Based on Disruptive Selection for Examination Timetabling Problems / Salwani Abdullah
• Heuristics for Parallel Machine Scheduling with Deterioration Effect / Lu Wang
• Comprehensive Study of an Online Packet Scheduling Algorithm / Fei Li
• Optimal Policy for Single-Machine Scheduling with Deterioration Effects, Learning Effects, Setup Times, and Availability Constraints / Feifeng Zheng
• Algebraic Algorithm for Scheduling Data Retrieval in Multi-channel Wireless Data Broadcast Environments / Bin Fu
• Hamiltonian Cycles through Prescribed Edges in k-Ary n-Cubes / Iain A. Stewart
• Fast Parallel Algorithm for Finding a Most Reliable Source on a General Ring-Tree Graph with Unreliable Edges / Guoliang Xue
• Restricted Edge Connectivity of Harary Graphs / Zhao Zhang
• Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem / Daniel Vanderpooten
• Euclidean Chains and Their Shortcuts / Boting Yang
• List Dynamic Coloring of Sparse Graphs / Won-Jin Park
• Further Improvement on Maximum Independent Set in Degree-4 Graphs / Hiroshi Nagamochi
• Approximation Algorithms for Minimum Energy Multicast Routing with Reception Cost in Wireless Sensor Networks / Wenping Chen
• Public Communication Based on Russian Cards Protocol: A Case Study / Zhenhua Duan
• Minimum Latency Data Aggregation in Wireless Sensor Network with Directional Antenna / Xianling Lu
• Near-Optimal Memoryless Online Algorithm for FIFO Buffering Two Packet Classes / Fei Li
• On the Maximum Locally Clustered Subgraph and Some Related Problems / Bang Ye Wu
• Quickest Paths in Anisotropic Media / Joachim Gudmundsson

• Note continued:
• Mechanisms for Obnoxious Facility Game on a Path / Guochuan Zhang
• Algorithmic Aspects of Heterogeneous Biological Networks Comparison / Stephane Vialette
• Minimum Interval Cover and Its Application to Genome Sequencing / Binhai Zhu
• Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem / Binhai Zhu
• Complexity of the Stamp Folding Problem / Hiro Ito
• On the Number of Solutions of the Discretizable Molecular Distance Geometry Problem / Antonio Mucherino
• Integration of an LP Solver into Interval Constraint Propagation / Stefan Kupferschmid
• Saturation Algorithm for Homogeneous Binomial Ideals / Shashank K. Mehta
• Improved Algorithms for Farthest Colored Voronoi Diagram of Segments / Jinhui Xu
• One-and-a-Half-Side Boundary Labeling / Hsu-Chun Yen
• Approximation Algorithms for a Bi-level Knapsack Problem / Guochuan Zhang
• On the Surface Area of the Asymmetric Twisted Cube / Zhizhang Shen
• Tractable Feedback Vertex Sets in Restricted Bipartite Graphs / Ke Xu
• On the Partition of 3-Colorable Graphs / Qing Wang
• Kinetic Red-Blue Minimum Separating Circle / Marko Zivanic
• Semantic Model for Many-Core Parallel Computing / Zhenhua Duan
• On Unique Games with Negative Weights / Ke Xu
• Note on Treewidth in Random Graphs / Ke Xu
• On the Two-Stage Stochastic Graph Partitioning Problem / Panos M. Pardalos
• Spatio-Temporal Approach to the Discovery of Online Social Trends / Jie Wang
• New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design / Peng Zhang
• Greedy Algorithm for Least Privilege in RBAC Model / Hongwei Du
• Towards Minimum Delay Broadcasting and Multicasting in Multihop Wireless Networks / Quanmin Ye.

This book constitutes the refereed proceedings of the 5th International Conference on Combinatorial Optimization and Applications, COCOA 2011, held in Zhangjiajie, China, in August 2011. The 43 revised full papers were carefully reviewed and selected from 65 submissions. The papers cover a broad range of topics in combinatorial optimization and applications focussing on experimental and applied research of general algorithmic interest and research motivated by real-world problems.
(source: Nielsen Book Data)

• Coverage with k-Transmitters in the Presence of Obstacles.- On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem.- Reducing the Maximum Latency of Selfish Ring Routing via Pairwise Cooperations.- Constrained Surface-Level Gateway Placement for Underwater Acoustic Wireless Sensor Networks.- Time Optimal Algorithms for Black Hole Search in Rings.- Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle.- A Constant-Factor Approximation Algorithm for the Link Building Problem.- XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme.- Computational Study for Planar Connected Dominating Set Problem.- Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives.- A Search-Based Approach to the Railway Rolling Stock Allocation Problem.- Approximation Algorithm for the Minimum Directed Tree Cover.- An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs.- A New Result on [k, k?+?1]-Factors Containing Given Hamiltonian Cycles.- Yao Graphs Span Theta Graphs.- A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n 2logn) Expected Time.- New Min-Max Theorems for Weakly Chordal and Dually Chordal Graphs.- A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem.- Fast Edge-Searching and Related Problems.- Diameter-Constrained Steiner Tree.- Minimizing the Maximum Duty for Connectivity in Multi-Interface Networks.- A Divide-and-Conquer Algorithm for Computing a Most Reliable Source on an Unreliable Ring-Embedded Tree.- Constrained Low-Interference Relay Node Deployment for Underwater Acoustic Wireless Sensor Networks.- Structured Overlay Network for File Distribution.- Optimal Balancing of Satellite Queues in Packet Transmission to Ground Stations.- The Networked Common Goods Game.- A Novel Branching Strategy for Parameterized Graph Modification Problems.- Listing Triconnected Rooted Plane Graphs.- Bipartite Permutation Graphs Are Reconstructible.- A Transformation from PPTL to S1S.- Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs.- Approximate Ellipsoid in the Streaming Model.
• (source: Nielsen Book Data)

The 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010) took place in Big Island, Hawaii, USA, December 18-20, 2010. Past COCOA conferences were held in Xi'an, China (2007), Newfoundland, Canada (2008)and Huangshan, China (2009). COCOA2010providedaforumforresearchersworkingintheareasofcom- natorial optimization and its applications. In addition to theoretical results, the conference also included recent works on experimental and applied research of general algorithmic interest. The Program Committee received 108 submissions from more than 23 countries and regions, including Australia, Austria, Canada, China, Denmark, France, Germany, Hong Kong, India, Italy, Japan, Korea, Mexico, New Zealand, Poland, Slovak Republic, Spain, Sweden, Switzerland, Taiwan, UK, USA, Vietnam, etc. Among the 108 submissions, 49 regular papers were selected for presentation at the conference and are included in this volume. Some of these papers will be selected for publication in a special issue of the Journal of Combinatorial Optimization, a special issue of Theoretical Computer Science, a special issue of Optimization Letters, and a special issue of Discrete Mathematics, Algorithms and Applications under the standard refereeing procedure.
(source: Nielsen Book Data)

This book constitutes the refereed proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008, held in Bertinoro, Italy, in May 2008. The 32 revised full papers presented were carefully reviewed and selected from 95 submissions. The papers cover various aspects of integer programming and combinatorial optimization and present recent developments in theory, computation, and applications in that area. Topics included are such as approximation algorithms, branch and bound algorithms, branch and cut algorithms, computational biology, computational complexity, computational geometry, cutting plane algorithms, diophantine equations, geometry of numbers, graph and network algorithms, integer programming, matroids and submodular functions, on-line algorithms and competitive analysis, polyhedral combinatorics, randomized algorithms, random graphs, scheduling theory and scheduling algorithms, and semidefinite programs.
(source: Nielsen Book Data)

• Invited Lecture.- Matchings in Graphs Variations of the Problem.- Combinatorics from Bacterial Genomes.- Contributed Papers.- An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces.- Finding the Anti-block Vital Edge of a Shortest Path Between Two Nodes.- K-Connected Target Coverage Problem in Wireless Sensor Networks.- Searching Cycle-Disjoint Graphs.- An Asymptotic PTAS for Batch Scheduling with Nonidentical Job Sizes to Minimize Makespan.- A New Dynamic Programming Algorithm for Multiple Sequence Alignment.- Energy Minimizing Vehicle Routing Problem.- On the On-Line k-Taxi Problem with Limited Look Ahead.- The Minimum Risk Spanning Tree Problem.- The Size of a Minimum Critically m-Neighbor-Scattered Graph.- A New Hybrid Algorithm for Feature Selection and Its Application to Customer Recognition.- Steiner Forests on Stochastic Metric Graphs.- On Threshold BDDs and the Optimal Variable Ordering Problem.- Communication Leading to Nash Equilibrium Through Robust Messages - S5-Knowledge Model Case -.- Fundamental Domains for Integer Programs with Symmetries.- Exact Algorithms for Generalized Combinatorial Optimization Problems.- Approximation Algorithms for k-Duplicates Combinatorial Auctions with Subadditive Bidders.- A Grid Resource Discovery Method Based on Adaptive k-Nearest Neighbors Clustering.- Algorithms for Minimum m-Connected k-Dominating Set Problem.- Worst Case Analysis of a New Lower Bound for Flow Shop Weighted Completion Time Problem.- Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp.- Mechanism Design by Creditability.- Infinite Families of Optimal Double-Loop Networks.- Point Sets in the Unit Square and Large Areas of Convex Hulls of Subsets of Points.- An Experimental Study of Compressed Indexing and Local Alignments of DNA.- Secure Multiparty Computations Using the 15 Puzzle.- A Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem.- Single Machine Common Due Window Scheduling with Controllable Job Processing Times.- A Lower Bound on Approximation Algorithms for the Closest Substring Problem.- A New Exact Algorithm for the Two-Sided Crossing Minimization Problem.- Improved Approximation Algorithm for Connected Facility Location Problems.- The Computational Complexity of Game Trees by Eigen-Distribution.- The Minimum All-Ones Problem for Graphs with Small Treewidth.- An Exact Algorithm Based on Chain Implication for the Min-CVCB Problem.- Arc Searching Digraphs Without Jumping.- On the Complexity of Some Colorful Problems Parameterized by Treewidth.- A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model.
• (source: Nielsen Book Data)

Running to almost 400 pages, and featuring more than 40 papers, this work on combinatorial optimization and applications will be seen as an important addition to the literature. It constitutes the refereed proceedings of the first International Conference on Combinatorial Optimization and Applications, COCOA 2007, held in Xi'an, China in August of that year. The 29 revised full papers presented together with 8 invited papers and 2 invited presentations were carefully reviewed and selected from 114 submissions and cover both theoretical issues and practical applications.
(source: Nielsen Book Data)

• Session 1.- Inequalities from Two Rows of a Simplex Tableau.- Cuts for Conic Mixed-Integer Programming.- Sequential-Merge Facets for Two-Dimensional Group Problems.- Session 2.- Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract).- The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization.- Finding a Polytope from Its Graph in Polynomial Time.- Session 3.- Orbitopal Fixing.- New Variants of Lift-and-Project Cut Generation from the LP Tableau: Open Source Implementation and Testing.- Orbital Branching.- Session 4.- Distinct Triangle Areas in a Planar Point Set.- Scheduling with Precedence Constraints of Low Fractional Dimension.- Approximation Algorithms for 2-Stage Stochastic Scheduling Problems.- Session 5.- On Integer Programming and the Branch-Width of the Constraint Matrix.- Matching Problems in Polymatroids Without Double Circuits.- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract).- Session 6.- On a Generalization of the Master Cyclic Group Polyhedron.- A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications.- On the Exact Separation of Mixed Integer Knapsack Cuts.- Session 7.- A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization.- On Convex Minimization over Base Polytopes.- Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems.- Session 8.- Generating Multiple Solutions for Mixed Integer Programming Problems.- A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations.- DINS, a MIP Improvement Heuristic.- Session 9.- Mixed-Integer Vertex Covers on Bipartite Graphs.- On the MIR Closure of Polyhedra.- The Intersection of Continuous Mixing Polyhedra and the Continuous Mixing Polyhedron with Flows.- Session 10.- Simple Explicit Formula for Counting Lattice Points of Polyhedra.- Characterizations of Total Dual Integrality.- Sign-Solvable Linear Complementarity Problems.- Session 11.- An Integer Programming Approach for Linear Programs with Probabilistic Constraints.- Infrastructure Leasing Problems.- Robust Combinatorial Optimization with Exponential Scenarios.- Session 12.- Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities.- Optimal Efficiency Guarantees for Network Design Mechanisms.- The Set Connector Problem in Graphs.
• (source: Nielsen Book Data)

This book constitutes the refereed proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2007, held in Ithaca, NY, USA, in June 2007. Among the topics addressed in the 36 revised full papers are approximation algorithms, algorithmic game theory, computational biology, integer programming, polyhedral combinatorics, scheduling theory and scheduling algorithms, as well as semidefinite programs.
(source: Nielsen Book Data)

This book constitutes the refereed proceedings for the 4th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2004, held in Coimbra, Portugal, in April together with EuroGP 2004 and six workshops on evolutionary computing. The 23 revised full papers presented were carefully reviewed and selected from 86 submissions. Among the topics addressed are evolutionary algorithms as well as metaheuristics like memetic algorithms, ant colony optimization, and scatter search; the papers are dealing with representations, operators, search spaces, adaptation, comparison of algorithms, hybridization of different methods, and theory. Among the combinatorial optimization problems studied are graph coloring, network design, cutting, packing, scheduling, timetabling, traveling salesman, vehicle routing, and various other real-world applications.
(source: Nielsen Book Data)