An application of simultaneous diophantine approximation in combinatorial optimization

DOI10.1007/BF02579200zbMath0641.90067WikidataQ56519176 ScholiaQ56519176MaRDI QIDQ1101013

Éva Tardos, András Frank

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

perfect graph; simultaneous Diophantine approximation; preprocessing; strongly polynomial time; maximum weight clique; minimum cost submodular flow

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

90C10: Integer programming

90B10: Deterministic network models in operations research

90C27: Combinatorial optimization

Related Items

A lower bound for the shortest path problem, Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring, Parameterized complexity of coloring problems: treewidth versus vertex cover, Approximation algorithms for group prize-collecting and location-routing problems, Test sets of integer programs, A separation algorithm for the matchable set polytope, A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball, A simplex algorithm for a class of Leontief flow problems, Short vectors of planar lattices via continued fractions, An asymptotically exact algorithm for the high-multiplicity bin packing problem, A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows, A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly polynomial minimum cost circulation algorithm
• Factoring polynomials with rational coefficients
• Minimization on submodular flows
• The ellipsoid method and its consequences in combinatorial optimization
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Integer Programming with a Fixed Number of Variables
• A Primal-Dual Algorithm for Submodular Flows
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• Packing and covering with integral feasible flows in integral supply-demand networks
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Systems of distinct representatives and linear algebra
• Minimum partition of a matroid into independent subsets