Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Budget Constraint
Combinatorial Optimization Problem
Lagrangian Relaxation
Maximum Weight Matching
Optimal Solution
Polynomial Time
Polynomial Time Approximation Scheme
Subscribe
Academic
Publications
Budgeted matching and budgeted matroid intersection via the gasoline puzzle
Budgeted matching and budgeted matroid intersection via the gasoline puzzle,10.1007/s1010700903074,Mathematical Programming,André Berger,Vincenzo B
Edit
Budgeted matching and budgeted matroid intersection via the gasoline puzzle
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
André Berger
,
Vincenzo Bonifaci
,
Fabrizio Grandoni
,
Guido Schäfer
Many polynomialtime solvable
combinatorial optimization
problems become NPhard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximumweight matching and maximumweight matroid intersection with one additional budget constraint. We present the first polynomialtime approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to the
Lagrangian relaxation
of the problem and patch them together to obtain a nearoptimal solution. However, due to the richer combinatorial structure of the problems considered here, standard patching techniques do not apply. To circumvent this problem, we crucially exploit the adjacency relations on the solution polytope and, surprisingly, the solution to an old combinatorial puzzle.
Journal:
Mathematical Programming
, vol. 128, no. 12, pp. 355372, 2011
DOI:
10.1007/s1010700903074
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
References
(39)
An algorithm for the resource constrained shortest path problem
(
Citations: 96
)
J. E. Beasley
,
N. Christofides
Journal:
Networks
, vol. 19, no. 4, pp. 379394, 1989
An application of lagrangean decomposition to the resourceconstrained minimum weighted arborescence problem
(
Citations: 11
)
Monique Guignard
,
Moshe B. Rosenwein
Journal:
Networks
, vol. 20, no. 3, pp. 345359, 1990
Approximating the MinimumDegree Steiner Tree to within One of Optimal
(
Citations: 2
)
M Furer
Journal:
Journal of Algorithms  JAL
, vol. 17, no. 3, pp. 409423, 1994
On matroid intersection adjacency
(
Citations: 2
)
Satoru Iwata
Journal:
Discrete Mathematics  DM
, vol. 242, no. 13, pp. 277281, 2002
The dependence graph for bases in matroids
(
Citations: 20
)
S Krogdahl
Journal:
Discrete Mathematics  DM
, vol. 19, no. 1, pp. 4759, 1977
Sort by:
Citations
(1)
Diagnosis of Catheterrelated Infections
(
Citations: 1
)
Heinrich K. Geiss
Journal:
Zentralblatt Fur Bakteriologieinternational Journal of Medical Microbiology Virology Parasitology and Infectious Diseases  ZBL BAKTINT J MED MICROBIOL
, vol. 283, no. 2, pp. 145153, 1995