An application of simultaneous diophantine approximation in combinatorial optimization

DOI10.1007/BF02579200zbMath0641.90067OpenAlexW2090960684WikidataQ56519176 ScholiaQ56519176MaRDI QIDQ1101013

Éva Tardos, András Frank

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579200

zbMATH Keywords

perfect graphsimultaneous Diophantine approximationpreprocessingstrongly polynomial timemaximum weight cliqueminimum cost submodular flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

On approximate data reduction for the Rural Postman Problem: Theory and experiments ⋮ 0/1-Integer programming: Optimization and Augmentation are equivalent ⋮ A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ On structural parameterizations of star coloring ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Complexity of optimizing over the integers ⋮ A strongly polynomial algorithm for the minimum maximum flow degree problem ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Extended MSO model checking via small vertex integrity ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Parameterized Complexity of Broadcasting in Graphs ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Tensors in computations ⋮ Parameterized Resiliency Problems via Integer Linear Programming ⋮ A separation algorithm for the matchable set polytope ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ A fast cost scaling algorithm for submodular flow ⋮ Even circuits in oriented matroids ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times ⋮ On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ Target Set Selection in Dense Graph Classes ⋮ Polynomial kernels for weighted problems ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ Solving MIPs via scaling-based augmentation ⋮ A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball ⋮ A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs ⋮ A simplex algorithm for a class of Leontief flow problems ⋮ No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines ⋮ Change-making problems revisited: a parameterized point of view ⋮ Parameterized complexity of configuration integer programs ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Integer programming in parameterized complexity: five miniatures ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Knapsack problems: a parameterized point of view ⋮ Dynamic coloring on restricted graph classes ⋮ Abstract tropical linear programming ⋮ Building large \(k\)-cores from sparse graphs ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Structural parameterization of cluster deletion ⋮ From approximate to exact integer programming ⋮ A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ On the complexity of quasiconvex integer minimization problem ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Parameterized multi-scenario single-machine scheduling problems ⋮ Unnamed Item ⋮ Approximation schemes for packing splittable items with cardinality constraints ⋮ On the string consensus problem and the Manhattan sequence consensus problem ⋮ Unnamed Item ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ Parameterized Complexity of Safe Set ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Multi-attribute proportional representation ⋮ The minimum feasible tileset problem ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ A scaling algorithm for optimizing arbitrary functions over vertices of polytopes ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Enumerating Projections of Integer Points in Unbounded Polyhedra ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ The complexity landscape of decompositional parameters for ILP ⋮ Swapping colored tokens on graphs ⋮ Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines ⋮ On the complexity of wafer-to-wafer integration ⋮ Parameterized complexity of asynchronous border minimization ⋮ Parameterizing by the number of numbers ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ On explaining integer vectors by few homogeneous segments ⋮ Finding vertex-surjective graph homomorphisms ⋮ A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A lower bound for the shortest path problem ⋮ Alliances in graphs of bounded clique-width ⋮ ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors ⋮ Partitioning graphs into induced subgraphs ⋮ Local linear set on graphs with bounded twin cover number ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Approximating vector scheduling: almost matching upper and lower bounds ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ Approximation algorithms for group prize-collecting and location-routing problems ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ Graph square roots of small distance from degree one graphs ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems

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

This page was built for publication: An application of simultaneous diophantine approximation in combinatorial optimization