NDLI: Primal-dual schema for capacitated covering problems

Content Provider	Springer Nature Link
Author	Shmoys, David B. Carnes, Tim
Copyright Year	2014
Abstract	Primal-dual algorithms have played an integral role in recent developments in approximation algorithms, and yet there has been little work on these algorithms in the context of LP relaxations that have been strengthened by the addition of more sophisticated valid inequalities. We introduce primal-dual schema based on the LP relaxations devised by Carr et al. for the minimum knapsack problem as well as for the single-demand capacitated facility location problem. Our primal-dual algorithms achieve the same performance guarantees as the LP-rounding algorithms of Carr et al. which rely on applying the ellipsoid algorithm to an exponentially-sized LP. Furthermore, we introduce new flow-cover inequalities to strengthen the LP relaxation of the more general capacitated single-item lot-sizing problem; using just these inequalities as the LP relaxation, we obtain a primal-dual algorithm that achieves a performance guarantee of 2. Computational experiments demonstrate the effectiveness of this algorithm on generated problem instances.
Ending Page	308
Page Count	20
Starting Page	289
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	2
Volume Number	153
Language	English
Publisher	Springer Berlin Heidelberg
Publisher Date	2014-08-15
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Lot-sizing Theoretical, Mathematical and Computational Physics Inventory, storage, reservoirs Linear programming Primal-dual schema Combinatorial optimization Mathematical Methods in Physics Calculus of Variations and Optimal Control; Optimization Mathematics of Computing Numerical Analysis Approximation algorithms Knapsack-cover inequalities Combinatorics
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Primal-dual schema for capacitated covering problems (2008).

Relaxations for two-level multi-item lot-sizing problems

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

Erratum: A tight formulation for uncapacitated lot-sizing with stock upper bounds

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

Second-order cover inequalities

On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique

Fixed-charge transportation on a path: optimization, LP formulations and separation

Approximation algorithms for supply chain planning and logistics problems with market choice

Primal-dual schema for capacitated covering problems

Similar Documents

Primal-dual schema for capacitated covering problems (2008).

Relaxations for two-level multi-item lot-sizing problems

A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems

Erratum: A tight formulation for uncapacitated lot-sizing with stock upper bounds

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

Second-order cover inequalities

On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique

Fixed-charge transportation on a path: optimization, LP formulations and separation

Approximation algorithms for supply chain planning and logistics problems with market choice

Primal-dual schema for capacitated covering problems