Titlebook: Research Trends in Combinatorial Optimization; Bonn 2008 William Cook,László Lovász,Jens Vygen Book 2009 Springer-Verlag Berlin Heidelberg

conceal

不如屎壳郎

,Strongly Polynomial Algorithm for the Intersection of a Line with a Polymatroid,ch generalizes the first algorithm and solves a parametric linear program. We prove that these two algorithms are strongly polynomial and that their running time is .(..+...) where . is the time for an oracle call. The second algorithm gives a polynomial algorithm to solve the submodular function mi

ABASH

A Survey on Covering Supermodular Functions,ons with supermodular or related properties. These include a wide range of network design and connectivity augmentation and orientation problems, as well as some results on colourings and matchings..In the first part of the paper we survey results that follow from the totally dual integral (TDI) pro

斗志

Theory of Principal Partitions Revisited,he early stage of the developments during 1967–75 the principal partition was considered as a decomposition of a discrete system into its components together with a partially ordered structure of the set of the components. It then turned out that such a decomposition with a partial order on it arise

AVOID

,Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach,arge girth. It combines a random outer procedure processing the graph in rounds with a virtually arbitrary algorithm solving local instances within each round and combines the local solutions to a global one. The local uniformity of the considered instances and the randomness of the outer procedure

拘留

,Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems,mples include problems in VLSI-design or problems in bioinformatics. For such problems the question arises: What is the best solution that can be obtained in linear time? We survey linear time approximation algorithms for some classical problems from combinatorial optimization, e.g. matchings and br

arthroplasty

The Unbounded Knapsack Problem,ng the periodic structure of the optimal solutions when the knapsack weight-carrying capacity . is sufficiently large. In addition to reviewing existing algorithms on the subject, the paper also includes two new algorithms, one for finding the onset of the optimal periodic solutions in time .(..), w

绅士

Recent Developments in Discrete Convex Analysis,nd M-convex functions in discrete and continuous variables. Expansion of the application areas is demonstrated by recent connections to submodular function maximization, finite metric space, eigenvalues of Hermitian matrices, discrete fixed point theorem, and matching games.

澄清

认识