scientific article; zbMATH DE number 3635849
From MaRDI portal
Publication:4196269
zbMath0408.90085MaRDI QIDQ4196269
Marshall L. Fisher, Laurence A. Wolsey, Nemhauser, George I.
Publication date: 1978
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
MatroidsLinear ProgrammingIndependence SystemsGreedy Heuristic AlgorithmSubmodular Set FunctionsWorst Case Behavior
Linear programming (90C05) Combinatorial aspects of matroids and geometric lattices (05B35) Numerical methods of relaxation type (49M20) Mathematical programming (90C99)
Related Items
Maximization of nonsubmodular functions under multiple constraints with applications, Distributed strategy selection: a submodular set function maximization approach, Two-stage BP maximization under \(p\)-matroid constraint, A single factor approximation ratio algorithm for DR-submodular maximization on integer lattice beyond non-negativity and monotonicity, Improved deterministic algorithms for non-monotone submodular maximization, Unified Greedy Approximability beyond Submodular Maximization, Improved deterministic algorithms for non-monotone submodular maximization, Streaming submodular maximization with the chance constraint, Unified greedy approximability beyond submodular maximization, Deterministic \(\boldsymbol{(\unicode{x00BD}+\varepsilon)}\) -Approximation for Submodular Maximization over a Matroid, Two-stage BP maximization under \(p\)-matroid constraint, Submodularity-based false data injection attack scheme in multi-agent dynamical systems, An exact solution approach for the mobile multi‐agent sensing problem, A Canonical Representation of Simple Plant Location Problems and Its Applications, The Limitations of Optimization from Samples, Faster approximation algorithms for maximizing a monotone submodular function subject to a \(b\)-matching constraint, The simulated greedy algorithm for several submodular matroid secretary problems, Streaming Algorithms for Submodular Function Maximization, The linking set problem: a polynomial special case of the multiple-choice knapsack problem, A multi-pass streaming algorithm for regularized submodular maximization, Policies for risk-aware sensor data collection by mobile agents, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Fractional 0-1 programming and submodularity, A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems, Directed submodularity, ditroids and directed submodular flows, Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order, Structured Robust Submodular Maximization: Offline and Online Algorithms, The Power of Subsampling in Submodular Maximization, A Framework for the Secretary Problem on the Intersection of Matroids, A sub-modular receding horizon solution for mobile multi-agent persistent monitoring, Quality of local equilibria in discrete exchange economies, A mobile multi-agent sensing problem with submodular functions under a partition matroid, Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid, Optimization with demand oracles, Optimal composition of heterogeneous multi-agent teams for coverage problems with performance bound guarantees, An accelerated continuous greedy algorithm for maximizing strong submodular functions, Thresholded covering algorithms for robust and max-min optimization, A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice, FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective, Selecting energy efficient inputs using graph structure, Constrained Submodular Maximization via a Nonsymmetric Technique, Submodular Maximization Through the Lens of Linear Programming, Matroid matching and some applications, Improved bounds for the greedy strategy in optimization problems with curvature, Unnamed Item, Approximation schemes for generalized two-dimensional vector packing with application to data placement, Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems, Submodular optimization problems and greedy strategies: a survey, Unnamed Item, Interactive optimization of submodular functions under matroid constraints, Greedy guarantees for non-submodular function maximization under independent system constraint with applications, Recent Developments in Discrete Convex Analysis, Inequalities on submodular functions via term rewriting, Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint, Stochastic block-coordinate gradient projection algorithms for submodular maximization, Maximize a monotone function with a generic submodularity ratio, Approximating max-min weighted \(T\)-joins, Is submodularity testable?, A \(k\)-product uncapacitated facility location problem, When Are Welfare Guarantees Robust, Exploiting submodularity to quantify near-optimality in multi-agent coverage problems, Valuated matroid-based algorithm for submodular welfare problem, The Submodular Secretary Problem Goes Linear, Online budgeted maximum coverage, Buyback Problem - Approximate Matroid Intersection with Cancellation Costs, Maximizing a submodular function with viability constraints, On maximizing a monotone \(k\)-submodular function subject to a matroid constraint, New performance guarantees for the greedy maximization of submodular set functions, IP over 40+ years at IBM scientific centers and marketing, Evaluation of Combinatorial Optimisation Algorithms for c-Optimal Experimental Designs with Correlated Observations, Parametric monotone function maximization with matroid constraints, Video distribution under multiple constraints, Randomized priority algorithms, Non-monotone submodular function maximization under \(k\)-system constraint, Unnamed Item, Unnamed Item, Combinatorial auctions with decreasing marginal utilities, Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions, Performance bounds with curvature for batched greedy optimization, A constructive proof of swap local search worst-case instances for the maximum coverage problem, Approximation for maximizing monotone non-decreasing set functions with a greedy method, Monotone submodular maximization over the bounded integer lattice with cardinality constraints, Robust Independence Systems, Maximizing monotone submodular functions over the integer lattice, Constrained submodular maximization via greedy local search, Online submodular maximization: beating 1/2 made simple, Approximate multi-matroid intersection via iterative refinement, Novel algorithms for maximum DS decomposition, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Two-stage submodular maximization under curvature, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Set function optimization, Multi-pass streaming algorithms for monotone submodular function maximization, An ex-post bound on the greedy heuristic for the uncapacitated facility location problem, The simple plant location problem: Survey and synthesis, A note on submodular set cover on matroids, Stability and Recovery for Independence Systems, Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem, On a class of covering problems with variable capacities in wireless networks, A heuristic lagrangean algorithm for the capacitated plant location problem, Unnamed Item, Improved algorithms for non-submodular function maximization problem, Informative path planning as a maximum traveling salesman problem with submodular rewards, Who should get vaccinated? Individualized allocation of vaccines over SIR network, An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint, Non-Submodular Maximization with Matroid and Knapsack Constraints, Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice, Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint, Logical processing for integer programming
