Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

No abstract is available for this paper.

• Publication year

  2004

• Venue

  Journal of combinatorial optimization

• Publication date

  2004-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1023/B:JOCO.0000038913.96607.c2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Convex quadratic and semidefinite programming relaxations in scheduling

  2001cited by this paper
• New 3⁄4 - Approximation Algorithms for MAX SAT

  2001cited by this paper
• An Approximation Algorithm for Max p-Section

  1999cited by this paper
• An Approximation Algorithm for Hypergraph Max k-Cut with Given Sizes of Parts

  1999cited by this paper
• Optimal scheduling of multiclass parallel machines

  1999cited by this paper
• The Budgeted Maximum Coverage Problem

  1999cited by this paper
• Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts

  1999cited by this paper
• Semidefinite relaxations for parallel machine scheduling

  1998influential reference
• Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT

  1998cited by this paper
• Using quadratic programming to solve high multiplicity scheduling problems on parallel machines

  1997cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems

  1996cited by this paper
• Polynomial time approximation schemes for dense instances of NP-hard problems

  1995cited by this paper
• Improved approximation algorithms for MAXk-CUT and MAX BISECTION

  1995cited by this paper
• New 3/4-Approximation Algorithms for the Maximum Satisfiability Problem

  1994cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988cited by this paper
• Approximation Algorithms for the Set Covering and Vertex Cover Problems

  1982cited by this paper
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems

  1982cited by this paper
• A Linear-Time Approximation Algorithm for the Weighted Vertex Cover Problem

  1981cited by this paper
• Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem

  1980cited by this paper
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms

  1977cited by this paper
• Approximate Algorithms for the 0/1 Knapsack Problem

  1975cited by this paper
• Various optimizers for single‐stage production

  1956cited by this paper

• Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback

  2026cites this paper
• SPICE: Submodular Penalized Information-Conflict Selection for Efficient Large Language Model Training

  2026cites this paper
• Approximation algorithm for extracting densest subgraph over matching-like constraints

  2026cites this paper
• Submodular Maximization Subject to Uniform and Partition Matroids: From Theory to Practical Applications and Distributed Solutions

  2025cites this paper
• Partitioning and Observability in Linear Systems via Submodular Optimization

  2025cites this paper
• Toward auction-based edge AI: Orchestrating and incentivizing online transfer learning in edge networks

  2025cites this paper
• Approximation algorithm for fair stochastic maximum coverage problem

  2025cites this paper
• Speed-Aware Network Design: A Parametric Optimization Approach

  2025cites this paper
• Improved Online Load Balancing in the Two-Norm

  2025cites this paper
• Fair Submodular Maximization over a Knapsack Constraint

  2025cites this paper
• Max-Cut with Multiple Cardinality Constraints

  2025influential citation
• Randomized Rounding over Dynamic Programs

  2025cites this paper
• Generalized Concentration-Based Performance Guarantees on Sensor Selection for State Estimation

  2025cites this paper
• Metric Distortion of Small-Group Deliberation

  2025cites this paper
• Verification of Sequential Convex Programming for Parametric Non-convex Optimization

  2025cites this paper
• Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps

  2025cites this paper
• Subquadratic Submodular Maximization with a General Matroid Constraint

  2024cites this paper
• Joint Power Control and Caching for Transmission Delay Minimization in Wireless HetNets

  2024cites this paper
• Online and Predictive Coordinated Cloud-Edge Scrubbing for DDoS Mitigation

  2024cites this paper
• Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back

  2024cites this paper
• Congestion-aware Routing and Content Placement in Elastic Cache Networks

  2024cites this paper
• Harm Mitigation in Recommender Systems under User Preference Dynamics

  2024cites this paper
• Balancing Total Energy Consumption and Mean Makespan in Data Offloading for Space-Air-Ground Integrated Networks

  2024cites this paper
• Energy Minimization via Joint Caching and Power Control in Wireless Heterogeneous Networks

  2024cites this paper
• Team Formation amidst Conflicts

  2024influential citation
• Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint

  2024influential citation
• A self-supervised learning model for graph clustering optimization problems

  2024cites this paper
• Federated Assemblies

  2024cites this paper
• Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint

  2024cites this paper
• Experimental Design Networks: A Paradigm for Serving Heterogeneous Learners Under Networking Constraints

  2023cites this paper
• 1/2 Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

  2023cites this paper
• Muster: Multi-Source Streaming for Tile-Based 360° Videos Within Cloud Native 5G Networks

  2023cites this paper
• Cost-Efficient Scheduling of Multicast Transfers With Deadline Guarantees Across Edge Datacenters

  2023cites this paper
• Joint Optimization of Storage and Transmission via Coding Traffic Flows for Content Distribution

  2023cites this paper
• Online Submodular Maximization via Online Convex Optimization

  2023influential citation
• On the Cost of Demographic Parity in Influence Maximization

  2023cites this paper
• Last Truck Scheduling for Middle-mile Next-day Delivery Coverage

  2023influential citation
• Parameterized Matroid-Constrained Maximum Coverage

  2023cites this paper
• Stochastic Submodular Maximization via Polynomial Estimators

  2023cites this paper
• Achieving Long-term Fairness in Submodular Maximization through Randomization

  2023cites this paper
• Supermodular Rank: Set Function Decomposition and Optimization

  2023influential citation
• Congestion-Aware Routing and Content Placement in Elastic Cache Networks

  2023cites this paper
• Cost-Efficient Cloud-Edge Video Analytics with Hybird IaaS and FaaS Resources

  2023cites this paper
• Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints

  2023influential citation
• Joint Application Placement and Request Routing Optimization for Dynamic Edge Computing Service Management

  2022cites this paper
• On-Demand or On-Premises: Online Mitigation of DDoS Attacks via Cloud-Edge Coordination

  2022cites this paper
• Experimental Design Networks: A Paradigm for Serving Heterogeneous Learners under Networking Constraints

  2022cites this paper
• Maximizing Modular plus Non-monotone Submodular Functions

  2022cites this paper
• GreenEdge: Joint Green Energy Scheduling and Dynamic Task Offloading in Multi-Tier Edge Computing Systems

  2022cites this paper
• Joint Caching and Routing in Cache Networks With Arbitrary Topology

  2022cites this paper
• In This Apportionment Lottery, the House Always Wins

  2022cites this paper
• Non-smooth and Hölder-smooth Submodular Maximization

  2022cites this paper
• Distributed submodular maximization: trading performance for privacy

  2022cites this paper
• A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice

  2022cites this paper
• Edge Resource Autoscaling for Hierarchical Federated Learning Over Public Edge Platforms

  2022cites this paper
• Algorithms for covering multiple submodular constraints and applications

  2022cites this paper
• An Improved Approximation Guarantee for Prize-Collecting TSP

  2022cites this paper
• Non-Smooth, H\"older-Smooth, and Robust Submodular Maximization

  2022cites this paper
• Online Caching Networks with Adversarial Guarantees

  2022cites this paper
• Density Personalized Group Query

  2022influential citation
• On the correlation gap of matroids

  2022influential citation
• Maximum Coverage in the Data Stream Model: Parameterized and Generalized

  2021cites this paper
• Incentive-Based D2D Relaying in Cellular Networks

  2021cites this paper
• Online Budgeted Maximum Coverage

  2021cites this paper
• Optimizing the Maximum Vertex Coverage Attacks Under Knapsack Constraint

  2021influential citation
• Matching Theory Under Uncertainty

  2021cites this paper
• Submodular Maximization via Taylor Series Approximation

  2021influential citation
• Siting renewable power generation assets with combinatorial optimisation

  2021cites this paper
• Constrained Robust Submodular Partitioning

  2021cites this paper
• Jointly Optimizing Throughput and Content Delivery Cost Over Lossy Cache Networks

  2021cites this paper
• Latency-aware Batch Task Offloading for Vehicular Cloud: Maximizing Submodular Bandit

  2021cites this paper
• Cache Networks of Counting Queues

  2021cites this paper
• Multilinear extension of k-submodular functions

  2021cites this paper
• Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

  2021cites this paper
• Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice

  2021cites this paper
• Joint User Association and Caching in Wireless Heterogeneous Networks with Backhaul

  2021cites this paper
• Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)

  2021cites this paper
• Information Resilience in a Network of Caches With Perturbations

  2021cites this paper
• Fast algorithms for maximizing monotone nonsubmodular functions

  2021cites this paper
• A fractional memory-efficient approach for online continuous-time influence maximization

  2021cites this paper
• Federated Learning with Fair Worker Selection: A Multi-Round Submodular Maximization Approach

  2021cites this paper
• An Auction Based Task Dispatching and Pricing Mechanism in Bike-sharing

  2021cites this paper
• Scalable Projection-Free Optimization

  2021cites this paper
• Transmission Delay Minimization via Joint Power Control and Caching in Wireless HetNets

  2021cites this paper
• Spatial Concentration of Caching in Wireless Heterogeneous Networks

  2021cites this paper
• Online Caching Networks with Adversarial Guarantees

  2021cites this paper
• Distributed Strategy Selection: A Submodular Set Function Maximization Approach

  2021cites this paper
• Continuous Submodular Function Maximization

  2020cites this paper
• Spatial Concentration of Caching

  2020cites this paper
• Provable Guarantees for General Two-sided Sequential Matching Markets

  2020cites this paper
• Appendix of Learning to Select Base Classes for Few-shot Classification 1. Proof of the Main Theories

  2020cites this paper
• Tight Approximation for Proportional Approval Voting

  2020cites this paper
• Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique

  2020influential citation
• Kelly Cache Networks

  2020influential citation
• Learning to Select Base Classes for Few-Shot Classification

  2020influential citation
• Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings

  2020cites this paper
• Influence-Based Community Partition With Sandwich Method for Social Networks

  2020cites this paper
• Balancing Coverage and Response Time in Area Target Scheduling for Satellite Networks

  2020influential citation
• Multi-Agent Maximization of a Monotone Submodular Function via Maximum Consensus

  2020cites this paper
• Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives

  2020influential citation