Approximation algorithms for classification problems with pairwise relationships
From MaRDI portal
Publication:3455544
DOI10.1145/585265.585268zbMath1326.68336OpenAlexW2061130579MaRDI QIDQ3455544
Publication date: 7 December 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/585265.585268
Random fields (60G60) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Pattern recognition, speech recognition (68T10) Approximation algorithms (68W25)
Related Items
The Boolean quadratic programming problem with generalized upper bound constraints ⋮ Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems ⋮ Inference methods for CRFs with co-occurrence statistics ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints ⋮ Minimizing energies with hierarchical costs ⋮ Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time ⋮ On discrete preferences and coordination ⋮ Stochastic approximation of lamplighter metrics ⋮ Fast approximate energy minimization with label costs ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Wasserstein distance and metric trees ⋮ Unnamed Item ⋮ A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case ⋮ Coupling from the past for exponentially ergodic one-dimensional probabilistic cellular automata ⋮ Unnamed Item ⋮ An improved algorithm for fixed-hub single allocation problems ⋮ Sperner’s Colorings and Optimal Partitioning of the Simplex ⋮ Convex variational methods on graphs for multiclass segmentation of high-dimensional data and point clouds ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Advances in metric embedding theory ⋮ Lifting Methods for Manifold-Valued Variational Problems ⋮ Assignment Flows ⋮ Algorithmic aspects of homophyly of networks ⋮ Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions ⋮ Submodular Cost Allocation Problem and Applications ⋮ Sublinear update time randomized algorithms for dynamic graph regression ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model ⋮ Discrete and continuous models for partitioning problems ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ How bad is forming your own opinion? ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Semi-supervised graph clustering: a kernel approach ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ Optimality of Correlated Sampling Strategies ⋮ A study of the quadratic semi-assignment polytope ⋮ Exact algorithms for a discrete metric labeling problem ⋮ Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems ⋮ Retracting Graphs to Cycles ⋮ Diffusion methods for classification with pairwise relationships ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Efficient Relaxations for Dense CRFs with Sparse Higher-Order Potentials ⋮ Empathetic decision making in social networks ⋮ Communication Complexity of Statistical Distance ⋮ On the theory of dynamic graph regression problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation Algorithms for the Single Allocation Problem in Hub-and-Spoke Networks
