Hardness and approximation of submodular minimum linear ordering problems
type: Item
instance of: scholarly article
title: Hardness and approximation of submodular minimum linear ordering problems
author: Majid Farhadi
author: Swati Gupta
author: Shengding Sun
author: Prasad Tetali
author: Michael C. Wigal
published in: Mathematical Programming. Series A. Series B
publication date: 2024-11-07T00:00:00Z
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7940321
zbMATH Keywords: minimum linear ordering problem
zbMATH Keywords: submodular
zbMATH Keywords: principal partitions
zbMATH Keywords: complexity
zbMATH Keywords: approximation
MaRDI profile type: MaRDI publication profile
cites work: Approximating Minimum Linear Ordering Problems
cites work: Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
cites work: Matroids and Graphs
cites work: Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
cites work: Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
cites work: Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
cites work: On the approximability of single-machine scheduling with precedence constraints
cites work: Q4904150
cites work: Q4250148
cites work: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
cites work: Theory of Principal Partitions Revisited
cites work: The boundaries of submodular functions
cites work: On Submodular Search and Machine Scheduling
cites work: Optimal Assignments of Numbers to Vertices
cites work: A Minimum Linear Arrangement Algorithm for Undirected Trees
cites work: On optimal linear arrangements of trees
cites work: An improved approximation ratio for the minimum linear arrangement problem
cites work: \(\ell ^2_2\) spreading metrics for vertex ordering problems
cites work: On the complexity of \(k\)-SAT
cites work: Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
cites work: Multiple intents re-ranking
cites work: Approximating min sum set cover
cites work: Algorithms – ESA 2005
cites work: Q4037408
cites work: Profile minimization problem for matrices and graphs
cites work: Q6147312
cites work: New Approximation Techniques for Some Linear Ordering Problems
cites work: A projected gradient algorithm for solving the maxcut SDP relaxation
cites work: Q5417729
cites work: A note on the generalized min-sum set cover problem
cites work: Preemptive and non-preemptive generalized min sum set cover
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The principal lattice of partitions of a submodular function
cites work: On the Complexity of Some Enumeration Problems for Matroids
cites work: Optimal Long Code Test with One Free Bit
cites work: Single-Machine Scheduling with Precedence Constraints
cites work: Single machine precedence constrained scheduling is a Vertex cover problem
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Fractional dimension of partial orders
cites work: Iterative Methods in Combinatorial Optimization
cites work: LINEAR LAYOUT OF GENERALIZED HYPERCUBES
cites work: Q3893961
DOI: 10.1007/S10107-023-02038-Z
description: scientific article; zbMATH DE number 7940321