No article text was recorded for this version.
linear programming relaxation
Version 1 of 11,042 papers1,300 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
- Blog: When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
- Blog: Fractional path coloring on bounded degree trees
- Blog: On the Hitting Set of Bundles Problem
- Blog: Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms
- Blog: Online Packing and Covering Framework with Convex Objectives
- Blog: Randomized Pipage Rounding for Matroid Polytopes and Applications
- Blog: A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: Star metric case
- Blog: LP-rounding algorithms for facility-location problems
- Blog: A Constant-Factor Approximation for Generalized Malleable Scheduling Under $M^\natural $-Concave Processing Speeds
- Blog: AdCell: Ad Allocation in Cellular Networks
- Blog: Symmetry-free SDP Relaxations for Affine Subspace Clustering
- Blog: A Lottery Model for Center-Type Problems With Outliers
- Blog: Generalized assignment problem: Truthful mechanism design without money
- Blog: Brief announcement: deadline-aware scheduling of big-data processing jobs
- Blog: Near-Optimal Truthful Auction Mechanisms in Secondary Spectrum Markets
- Blog: Scheduling with Outliers
- Blog: An Improved Algorithm for Fixed-Hub Single Allocation Problem
- Blog: LP rounding and combinatorial algorithms for minimizing active and busy time
- Blog: A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations
- Blog: Generalized Unrelated Machine Scheduling Problem
- Blog: Clustering on k-Edge-Colored Graphs
- Blog: Scheduling (Dagstuhl Seminar 16081)
- Blog: Truthfulness via Proxies
- Blog: Approximation results for a bicriteria job scheduling problem on a single machine without preemption
- Blog: Improved Approximations for Ultrametric Violation Distance
- Blog: Maximizing coverage while ensuring fairness: a tale of conflicting objective
- Blog: A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming
- Blog: Approximate Deadline-Scheduling with Precedence Constraints
- Blog: Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
- Blog: On (1, ∊)-Restricted Assignment Makespan Minimization
- Blog: Improved Approximations for Unrelated Machine Scheduling
- Blog: Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
- Blog: Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints
- Blog: Energy Efficient Scheduling and Routing via Randomized Rounding
- Blog: A Practical Distributed ADMM Solver for Billion-Scale Generalized Assignment Problems
- Blog: A Lottery Model for Center-Type Problems With Outliers
- Blog: The Alternating Stock Size Problem and the Gasoline Puzzle
- Blog: Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
- Blog: Joint Service Placement and Request Routing in Multi-cell Mobile Edge Computing Networks
- Blog: Pricing commodities
- Blog: Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
- Blog: Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems
- Blog: Towards Better-than-2 Approximation for Constrained Correlation Clustering
- Blog: Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms
- Blog: Approximation Algorithms for Online Weighted Rank Function Maximization\n under Matroid Constraints
- Blog: LP-Based Algorithms for Capacitated Facility Location
- Blog: A general approach to online network optimization problems
- Blog: Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design
- Blog: Improved Approximations for Unrelated Machine Scheduling
- Blog: On $(1, ε)$-Restricted Assignment Makespan Minimization
- Blog: Designing Effective and Practical Interventions to Contain Epidemics
- Blog: A Distributed Algorithm for Large-Scale Generalized Matching
- Blog: A unified continuous greedy algorithm for $k$-submodular maximization under a down-monotone constraint
- Blog: Limiting Disease Spreading in Human Networks
- Blog: Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching
- Blog: Rounding Methods for Discrete Linear Classification
- Blog: New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
- Blog: Core-Stable Committees under Restricted Domains
- Blog: Energy-efficient scheduling and routing via randomized rounding
Showing 60 of 1,042 papers.
History & citation
Current · Permanent link
- Continuous Relaxations and Randomized Rounding for Combinatorial Optimization merged into this direction (81% overlap)
- Bridging Integrality Gaps in Constrained Facility Location merged into this direction (50% overlap)
- Scheduling via Fractional Relaxation and Rounding merged into this direction (78% overlap)
- Approximation via Linear Programming Relaxation and Rounding merged into this direction (83% overlap)
Cite this direction
Latest version (a living page):
@misc{lacuna_linear_programming_relaxation_75e269fd,
title = {linear programming relaxation},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/linear-programming-relaxation/rdr_75e269fd92db42b09d8a011dc674242c},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}This exact version (version 1, frozen text):
@misc{lacuna_linear_programming_relaxation_75e269fd_v1,
title = {linear programming relaxation},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/linear-programming-relaxation/rdr_75e269fd92db42b09d8a011dc674242c/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}