Publication:4371290

William R. Pulleyblank, William H. Cunningham, William Cook, Alexander Schrijver

Publication date: 12 January 1998

shortest path matching NP-completeness matroids travelling salesman multicommodity flows minimum spanning tree network simplex dual scaling integrality of polyhedra

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

Tractable combinatorial auctions and \(b\)-matching, Cross line and column generation for the cut covering problem in wireless networks, Extending tournament solutions, Approximation algorithms for the \(k\)-depots Hamiltonian path problem, Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem, Generalized minor inequalities for the set covering polyhedron related to circulant matrices, The mixed evacuation problem, Scheduling with few changes, Optimal and Game-Theoretic Deployment of Security Investments in Interdependent Assets, Iteratively reweighted least squares and slime mold dynamics: connection and convergence, The computational complexity of the elimination problem in generalized sports competitions, A new heuristic for detecting non-Hamiltonicity in cubic graphs, How to collect balls moving in the Euclidean plane, Total dual dyadicness and dyadic generating sets, Revisiting a cutting-plane method for perfect matchings, On dominating set polyhedra of circular interval graphs, Finding all minimum cost flows and a faster algorithm for the \(K\) best flow problem, Structure theorem and algorithm on \((1,f)\)-odd subgraph, A simple LP relaxation for the asymmetric traveling salesman problem, A bilevel programming problem with maximization of a supermodular function in the lower level, Variable neighbourhood structures for cycle location problems, Exact and heuristic approaches for the cycle hub location problem, A history of graph entropy measures, Min Sum Edge Coloring in Multigraphs Via Configuration LP, Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank, Finding small stabilizers for unstable graphs, Optimality conditions for a bilevel matroid problem, Changing of the guards: strip cover with duty cycling, Query-competitive algorithms for cheapest set problems under uncertainty, Dominance rules in combinatorial optimization problems, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, \texttt{Procrustes}: a python library to find transformations that maximize the similarity between matrices, A detailed introduction to a minimum-cost perfect matching algorithm based on linear programming, A Survey on Covering Supermodular Functions, Recent Developments in Discrete Convex Analysis, Polynomial time approximation schemes for the constrained minimum spanning tree problem, On the approximability of some degree-constrained subgraph problems, A comparison of lower bounds for the symmetric circulant traveling salesman problem, Linearly-growing reductions of Karp's 21 NP-complete problems, A comparative study of two fast phase unwrapping algorithms., The essence of constraint propagation, Edge-disjoint odd cycles in planar graphs., Certifying algorithms, An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem, Approximation algorithms for partially covering with edges, Monotonizing linear programs with up to two nonzeroes per column, Bounding the payment of approximate truthful mechanisms, Using critical sets to solve the maximum independent set problem, Symmetric PMC model of diagnosis, \(b\)-matchings in graphs and fault identification in \(t\)-diagnosable systems, Capacitated Vehicle Routing with Non-uniform Speeds, Minimizing task completion time with the execution set method, Metric inequalities and the network loading problem, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs, \(V\)- and \(D\)-optimal population designs for the simple linear regression model with a random intercept term, The Erdős-Hajnal conjecture for bull-free graphs, Using combinatorial optimization in model-based trimmed clustering with cardinality constraints, Characterizations of postman sets, Graph connectivity and its augmentation: Applications of MA orderings, A class of network optimization methods for planar grid generation, Determination of the candidate arc set for the asymmetric traveling salesman problem, Workweek optimization of experimental designs: exact designs for variable sampling costs, Approximation algorithms for some vehicle routing problems, On minimum power connectivity problems, A factor \(\frac {1}{2}\) approximation algorithm for two-stage stochastic matching problems, On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection, Multiprocessor scheduling under precedence constraints: polyhedral results, A graph theoretic method for determining generating sets of prime ideals in quantum matrices, Alternative integer-linear-programming formulations of the Clar problem in hexagonal systems, Home service routing and appointment scheduling with stochastic service times, Facets of the independent path-matching polytope, Scheduling problems over a network of machines, Separation routine and extended formulations for the stable set problem in claw-free graphs, Stabilizing network bargaining games by blocking players, Even factors, jump systems, and discrete convexity, Generalized network design problems., Team formation: Matching quality supply and quality demand., Characterizing the flow equivalent trees of a network, Semi-automatically optimized calibration of internal combustion engines, Stabilizing Weighted Graphs, Fractional matching preclusion number of graphs and the perfect matching polytope, Parity and disparity subgraphs, Approximating minimum-power edge-covers and 2,3-connectivity, Reconstruction, optimization, and design of heterogeneous materials and media: basic principles, computational algorithms, and applications, Weighted coloring on planar, bipartite and split graphs: Complexity and approximation, On the maximum size of a minimal \(k\)-edge connected augmentation, Exact and approximation algorithms for weighted matroid intersection, Graphs and Algorithms in Communication Networks on Seven League Boots, A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix, Refined cut selection for Benders decomposition: applied to network capacity expansion problems, Using a greedy random adaptative search procedure to solve the cover printing problem, Extension of M-convexity and L-convexity to polyhedral convex functions, A note on diagonally dominant matrices, Towards an efficient resolution of printing problems, Enumerating colorings, tensions and flows in cell complexes, The minimum flow cost Hamiltonian cycle problem: a comparison of formulations, Approximation algorithms for multi-parameter graph optimization problems, Majorization-constrained doubly stochastic matrices, Partition-distance: A problem and class of perfect graphs arising in clustering, Compact vs. exponential-size LP relaxations, A weight-scaling algorithm for \(f\)-factors of multigraphs, Ehrhart theory of paving and panhandle matroids, Complementability of isometric copies of \(\ell_1\) in transportation cost spaces, An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems, On quantum optimal transport, One-Dimensional Carousel Storage Problems: Applications, Review and Generalizations, Domination mappings into the Hamming ball: existence, constructions, and algorithms, Exact separation of the rounded capacity inequalities for the capacitated vehicle routing problem, Orientability Thresholds for Random Hypergraphs, A Privacy-Preserving Method to Optimize Distributed Resource Allocation, Deriving compact extended formulations via LP-based separation techniques, Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach, Learning in Combinatorial Optimization: What and How to Explore, Scheduling Problems over Network of Machines, Quantum Strassen’s theorem, Interpolating greedy and reluctant algorithms, Applying an Intensification Strategy on Vehicle Routing Problem, Deriving compact extended formulations via LP-based separation techniques, Construction heuristics for the asymmetric TSP., Tree spanners in planar graphs, The new FIFA rules are hard: Complexity aspects of sports competitions., On circuit valuation of matroids, A cycle augmentation algorithm for minimum cost multicommodity flows on a ring, Elementary closures for integer programs., Structural Change and Homeostasis in Organizations: A Decision-Theoretic Approach, Set covering approach for reconstruction of sibling relationships, Algorithm for optimal winner determination in combinatorial auctions, Graph Stabilization: A Survey, The cable trench problem: Combining the shortest path and minimum spanning tree problems, Packing and covering odd cycles in cubic plane graphs with small faces, Approximate proof-labeling schemes, On the Approximability of Combinatorial Exchange Problems, Approximate multi-matroid intersection via iterative refinement, Hamiltonian threshold for strong products of graphs, Unnamed Item, Unnamed Item, Minimum Congestion Mapping in a Cloud, Unnamed Item, A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals