Pipage rounding: a new method of constructing algorithms with proven performance guarantee
From MaRDI portal
Publication:1888170
DOI10.1023/B:JOCO.0000038913.96607.c2zbMath1084.90029OpenAlexW2072291569MaRDI QIDQ1888170
Publication date: 22 November 2004
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/b:joco.0000038913.96607.c2
Approximation algorithmlinear relaxationperformance guaranteemaximum coveragemax cutrounding technique
Related Items (56)
Siting renewable power generation assets with combinatorial optimisation ⋮ Submodularity and Randomized rounding techniques for Optimal Experimental Design ⋮ Tight Approximation Bounds for Maximum Multi-coverage ⋮ Adding cardinality constraints to integer programs with applications to maximum satisfiability ⋮ Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex -- ⋮ Submodular Stochastic Probing on Matroids ⋮ Fairness in Influence Maximization through Randomization ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Structured Robust Submodular Maximization: Offline and Online Algorithms ⋮ Maximum coverage problem with group budget constraints ⋮ Multiple facility location on a network with linear reliability order of edges ⋮ Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline ⋮ An accelerated continuous greedy algorithm for maximizing strong submodular functions ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice ⋮ On the correlation gap of matroids ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Distributed strategy selection: a submodular set function maximization approach ⋮ Submodular Maximization Through the Lens of Linear Programming ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ The approximability of multiple facility location on directed networks with random arc failures ⋮ Tight approximation algorithms for ordered covering ⋮ A 6/5-approximation algorithm for the maximum 3-cover problem ⋮ Unnamed Item ⋮ Recent Developments in Discrete Convex Analysis ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ An efficient linear programming based method for the influence maximization problem in social networks ⋮ Near-optimal discrete optimization for experimental design: a regret minimization approach ⋮ Online budgeted maximum coverage ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ Mobile facility location: combinatorial filtering via weighted occupancy ⋮ Parametric monotone function maximization with matroid constraints ⋮ Video distribution under multiple constraints ⋮ How to allocate review tasks for robust ranking ⋮ Unnamed Item ⋮ Minimizing latency of capacitated \(k\)-tours ⋮ The complexity of bottleneck labeled graph problems ⋮ Approximation for maximizing monotone non-decreasing set functions with a greedy method ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ Price of dependence: stochastic submodular maximization with dependent items ⋮ ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS ⋮ Randomized Rounding in the Presence of a Cardinality Constraint ⋮ Maximization of submodular functions: theory and enumeration algorithms ⋮ On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Unnamed Item ⋮ A comment on scheduling two parallel machines with capacity constraints ⋮ Approximation algorithms for fragmenting a graph against a stochastically-located threat ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique ⋮ An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint ⋮ Packing under convex quadratic constraints ⋮ Tight approximation bounds for maximum multi-coverage
This page was built for publication: Pipage rounding: a new method of constructing algorithms with proven performance guarantee
