scientific article; zbMATH DE number 6297715

zbMath1288.05259MaRDI QIDQ5417632

Amin Saberi, Michel X. Goemans, Shayan Oveis Gharan, Arash Asadpour, Aleksander Mądry

Publication date: 22 May 2014

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

A constant-factor approximation for directed latency in quasi-polynomial time ⋮ Generalized maximum entropy estimation ⋮ Traveling salesman problems in temporal graphs ⋮ Random Walks in Polytopes and Negative Dependence ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Better s-t-Tours by Gao Trees ⋮ Constant Factor Approximation for ATSP with Two Edge Weights ⋮ An Improved Integrality Gap for Asymmetric TSP Paths ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ A simple LP relaxation for the asymmetric traveling salesman problem ⋮ A Spectral Approach to Network Design ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ Chain-constrained spanning trees ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Multi-criteria TSP: Min and Max combined ⋮ Thin trees in 8-edge-connected planar graphs ⋮ Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems ⋮ A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time ⋮ Approximating the minimum tour cover of a digraph ⋮ New inapproximability bounds for TSP ⋮ Tour recommendation for groups ⋮ Quell ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ The effect of the asymmetry of road transportation networks on the traveling salesman problem ⋮ The directed orienteering problem ⋮ Deterministic algorithms for multi-criteria max-TSP ⋮ On the core of traveling salesman games ⋮ No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem ⋮ Reassembling Trees for the Traveling Salesman ⋮ Approximating MIN-cost chain-constrained spanning trees: a reduction from weighted to unweighted problems ⋮ Better \(s-t\)-tours by Gao trees ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Thin trees in some families of distance-regular graphs ⋮ Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids ⋮ A General Framework for Graph Sparsification ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ Electrical flows over spanning trees ⋮ Unnamed Item