551 lines
36 KiB
BibTeX
551 lines
36 KiB
BibTeX
@article{Dyer84,
|
||
title = {An {{O}}(n) Algorithm for the Multiple-Choice Knapsack Linear Program},
|
||
author = {Dyer, M. E.},
|
||
year = {1984},
|
||
month = may,
|
||
journal = {Mathematical Programming},
|
||
volume = {29},
|
||
number = {1},
|
||
pages = {57--63},
|
||
issn = {0025-5610, 1436-4646},
|
||
doi = {10.1007/BF02591729},
|
||
langid = {english},
|
||
file = {/Users/chaoxu/Zotero/storage/RLSLWMGP/Dyer - 1984 - An O(n) algorithm for the multiple-choice knapsack.pdf}
|
||
}
|
||
|
||
@article{DavidPisinger,
|
||
title = {Budgeting with bounded multiple-choice constraints},
|
||
journal = {European Journal of Operational Research},
|
||
volume = {129},
|
||
number = {3},
|
||
pages = {471-480},
|
||
year = {2001},
|
||
issn = {0377-2217},
|
||
doi = {https://doi.org/10.1016/S0377-2217(99)00451-8},
|
||
url = {https://www.sciencedirect.com/science/article/pii/S0377221799004518},
|
||
author = {David Pisinger},
|
||
keywords = {Integer programming, Dantzig–Wolfe decomposition, Dynamic programming, Bounded multiple-choice knapsack problem},
|
||
abstract = {We consider a budgeting problem where a specified number of projects from some disjoint classes has to be selected such that the overall gain is largest possible, and such that the costs of the chosen projects do not exceed a fixed upper limit. The problem has several application in government budgeting, planning, and as relaxation from other combinatorial problems. It is demonstrated that the problem can be transformed to an equivalent multiple-choice knapsack problem through dynamic programming. A naive transformation however leads to a drastic increase in the number of variables, thus we propose an algorithm for the continuous problem based on Dantzig–Wolfe decomposition. A master problem solves a continuous multiple-choice knapsack problem knowing only some extreme points in each of the transformed classes. The individual subproblems find extreme points for each given direction, using a median search algorithm. An integer optimal solution is then derived by using the dynamic programming transformation to a multiple-choice knapsack problem for an expanding core. The individual classes are considered in an order given by their gradients, and the transformation to a multiple-choice knapsack problem is performed when needed. In this way, only a dozen of classes need to be transformed for standard instances from the literature. Computational experiments are presented, showing that the developed algorithm is orders of magnitude faster than a general LP/MIP algorithm.}
|
||
},
|
||
@article{CAMERINI1984157,
|
||
title = {The matroidal knapsack: A class of (often) well-solvable problems},
|
||
journal = {Operations Research Letters},
|
||
volume = {3},
|
||
number = {3},
|
||
pages = {157-162},
|
||
year = {1984},
|
||
issn = {0167-6377},
|
||
doi = {https://doi.org/10.1016/0167-6377(84)90009-9},
|
||
url = {https://www.sciencedirect.com/science/article/pii/0167637784900099},
|
||
author = {Paolo M. Camerini and Carlo Vercellis},
|
||
keywords = {knapsack problems, Lagrangean relaxation, matroids, probabilistic evaluation},
|
||
abstract = {A general class of problems, defined in terms of matroids, is recognized to include as special cases a variety of knapsack problems, subject to combinatorial constraints. A polynomial algorithm, based on Lagrangean relaxation, is proposed: A worst case and a probabilistic analysis demonstrate its ability to compute tight upper and lower bounds for the optimum, together with good approximate solutions.}
|
||
}
|
||
@article{Zoltners,
|
||
issn = {0030364X, 15265463},
|
||
url = {http://www.jstor.org/stable/170213},
|
||
abstract = {The multiple-choice knapsack problem is defined as a binary knapsack problem with the addition of disjoint multiple-choice constraints. The strength of the branch-and-bound algorithm we present for this problem resides with the quick solution of the linear programming relaxation and its efficient, subsequent reoptimization as a result of branching. An implemented version of this algorithm has performed well on a large set of test problems. We cite computational results as well as a comparison with a previously reported algorithm. Several useful applications of the multiple-choice knapsack problem are also suggested.},
|
||
author = {Prabhakant Sinha and Andris A. Zoltners},
|
||
journal = {Operations Research},
|
||
number = {3},
|
||
pages = {503--515},
|
||
publisher = {INFORMS},
|
||
title = {The Multiple-Choice Knapsack Problem},
|
||
urldate = {2022-11-06},
|
||
volume = {27},
|
||
year = {1979}
|
||
},
|
||
@unpublished{Chan1999RemarksOK,
|
||
title = {Remarks on k-Level Algorithms in the Plane},
|
||
author = {Timothy M. Chan},
|
||
year = {1999},
|
||
note = {Manuscript},
|
||
url = {https://tmc.web.engr.illinois.edu/pub_kset.html}
|
||
},
|
||
@inproceedings{10.1109/ITSC55140.2022.9922143,
|
||
author = {Javaudin, Lucas and Araldo, Andrea and de Palma, Andr\`{u}},
|
||
title = {Large-Scale Allocation of Personalized Incentives},
|
||
year = {2022},
|
||
publisher = {IEEE Press},
|
||
url = {https://doi.org/10.1109/ITSC55140.2022.9922143},
|
||
doi = {10.1109/ITSC55140.2022.9922143},
|
||
abstract = {We consider a regulator willing to drive individual choices towards increasing social welfare by providing incentives to a large population of individuals. For that purpose, we formalize and solve the problem of finding an optimal personalized-incentive policy: optimal in the sense that it maximizes social welfare under an incentive budget constraint, personalized in the sense that the incentives proposed depend on the alternatives available to each individual, as well as her preferences. We propose a polynomial time approximation algorithm that computes a policy within few seconds and we analytically prove that it is boundedly close to the optimum. We then extend the problem to efficiently calculate the Maximum Social Welfare Curve, which gives the maximum social welfare achievable for a range of incentive budgets (not just one value). This curve is a valuable practical tool for the regulator to determine the right incentive budget to invest. Finally, we simulate a large-scale application to mode choice in a French department (about 200 thousands individuals) and illustrate the effectiveness of the proposed personalized-incentive policy in reducing CO2 emissions.},
|
||
booktitle = {2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC)},
|
||
pages = {4151–4156},
|
||
numpages = {6},
|
||
location = {Macau, China}
|
||
}
|
||
@misc{wang_shmoys_2019,
|
||
title = {How to solve a linear optimization problem on incentive allocation?},
|
||
url = {https://eng.lyft.com/how-to-solve-a-linear-optimization-problem-on-incentive-allocation-5a8fb5d04db1},
|
||
journal = {Medium},
|
||
publisher = {Lyft Engineering},
|
||
author = {Wang, Shujing and Shmoys, David},
|
||
year = {2019},
|
||
month = {Sep}
|
||
}
|
||
@inbook{Kellerer2004,
|
||
author = {Kellerer, Hans
|
||
and Pferschy, Ulrich
|
||
and Pisinger, David},
|
||
title = {The Multiple-Choice Knapsack Problem},
|
||
booktitle = {Knapsack Problems},
|
||
year = {2004},
|
||
publisher = {Springer Berlin Heidelberg},
|
||
address = {Berlin, Heidelberg},
|
||
pages = {317--347},
|
||
abstract = {The multiple-choice knapsack problem (MCKP) is a generalization of the ordinary knapsack problem, where the set of items is partitioned into classes. The binary choice of taking an item is replaced by the selection of exactly one item out of each class of items. In Section 7.1 we already noticed that a (BKP) can be formulated as a (MCKP), and indeed the (MCKP) model is one of the most flexible knapsack models. (MCKP) is also denoted as knapsack problem with generalized upper bound constraints or for short knapsack problem with GUB.},
|
||
isbn = {978-3-540-24777-7},
|
||
doi = {10.1007/978-3-540-24777-7_11},
|
||
url = {https://doi.org/10.1007/978-3-540-24777-7_11}
|
||
},
|
||
@article{Eppstein98,
|
||
title = {Geometric {{Lower Bounds}} for {{Parametric Matroid Optimization}}},
|
||
author = {Eppstein, D.},
|
||
year = {1998},
|
||
month = dec,
|
||
journal = {Discrete \& Computational Geometry},
|
||
volume = {20},
|
||
number = {4},
|
||
pages = {463--476},
|
||
issn = {0179-5376},
|
||
doi = {10.1007/PL00009396},
|
||
langid = {english},
|
||
file = {/Users/chaoxu/Zotero/storage/QR8HQ64I/Eppstein - 1998 - Geometric Lower Bounds for Parametric Matroid Opti.pdf}
|
||
}
|
||
|
||
@article{ZEMEL1984123,
|
||
title = {An O(n) algorithm for the linear multiple choice knapsack problem and related problems},
|
||
journal = {Information Processing Letters},
|
||
volume = {18},
|
||
number = {3},
|
||
pages = {123-128},
|
||
year = {1984},
|
||
issn = {0020-0190},
|
||
doi = {https://doi.org/10.1016/0020-0190(84)90014-0},
|
||
url = {https://www.sciencedirect.com/science/article/pii/0020019084900140},
|
||
author = {Eitan Zemel},
|
||
keywords = {Linear programming, multiple choice knapsack, linear algorithms, least distance hyperplane},
|
||
abstract = {We present an O(n) algorithm for the Linear Multiple Choice Knapsack Problem and its d-dimensional generalization which is based on Megiddo's (1982) algorithm for linear programming. We also consider a certain type of convex programming problems which are common in geometric location models. An application of the linear case is an O(n) algorithm for finding a least distance hyperplane in Rd according to the rectilinear norm. The best previously available algorithm for this problem was an O(n log2n) algorithm for the two-dimensional case. A simple application of the nonlinear case is an O(n) algorithm for finding the point at which a ‘pursuer’ minimizes its distance from the furthest among n ‘targets’, when the trajectories involved are straight lines in Rd.}
|
||
},
|
||
@article{DyerOnalg,
|
||
title = {An O(n) algorithm for the multiple-choice knapsack linear program},
|
||
journal = {Mathematical Programming},
|
||
volume = {29},
|
||
pages = {57–63},
|
||
year = {1984},
|
||
doi = {https://doi.org/10.1007/BF02591729},
|
||
url = {https://www.sciencedirect.com/science/article/pii/0020019084900140},
|
||
author = {Dyer, M.E.}
|
||
},
|
||
@article{Carstensen83,
|
||
title = {Complexity of Some Parametric Integer and Network Programming Problems},
|
||
author = {Carstensen, Patricia J.},
|
||
year = {1983},
|
||
month = may,
|
||
journal = {Mathematical Programming},
|
||
volume = {26},
|
||
number = {1},
|
||
pages = {64--75},
|
||
issn = {0025-5610, 1436-4646},
|
||
doi = {10.1007/BF02591893},
|
||
abstract = {Two examples of parametric cost programming problems--one in network programming and one in NP-hard 0-1 programming--are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem.},
|
||
langid = {english},
|
||
file = {/Users/chaoxu/Zotero/storage/WUDD9HPG/Carstensen - 1983 - Complexity of some parametric integer and network .pdf}
|
||
}
|
||
@article{Zadeh73b,
|
||
title = {A Bad Network Problem for the Simplex Method and Other Minimum Cost Flow Algorithms},
|
||
author = {Zadeh, Norman},
|
||
year = {1973},
|
||
month = dec,
|
||
journal = {Mathematical Programming},
|
||
volume = {5},
|
||
number = {1},
|
||
pages = {255--266},
|
||
issn = {0025-5610, 1436-4646},
|
||
doi = {10.1007/BF01580132},
|
||
langid = {english}
|
||
}
|
||
@article{Murty80,
|
||
title = {Computational Complexity of Parametric Linear Programming},
|
||
author = {Murty, Katta G.},
|
||
year = {1980},
|
||
month = dec,
|
||
journal = {Mathematical Programming},
|
||
volume = {19},
|
||
number = {1},
|
||
pages = {213--219},
|
||
issn = {0025-5610, 1436-4646},
|
||
doi = {10.1007/BF01581642},
|
||
langid = {english}
|
||
}
|
||
@article{Megiddo,
|
||
author = {Megiddo, Nimrod},
|
||
title = {Applying Parallel Computation Algorithms in the Design of Serial Algorithms},
|
||
year = {1983},
|
||
issue_date = {Oct. 1983},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
volume = {30},
|
||
number = {4},
|
||
issn = {0004-5411},
|
||
url = {https://doi.org/10.1145/2157.322410},
|
||
doi = {10.1145/2157.322410},
|
||
journal = {J. ACM},
|
||
month = {oct},
|
||
pages = {852–865},
|
||
numpages = {14}
|
||
}
|
||
@article{Cole87,
|
||
title = {Slowing down Sorting Networks to Obtain Faster Sorting Algorithms},
|
||
author = {Cole, Richard},
|
||
year = {1987},
|
||
month = jan,
|
||
journal = {Journal of the ACM},
|
||
volume = {34},
|
||
number = {1},
|
||
pages = {200--208},
|
||
issn = {0004-5411, 1557-735X},
|
||
doi = {10.1145/7531.7537},
|
||
abstract = {Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of O (log n ) time (or more) for many applications of this technique.},
|
||
langid = {english},
|
||
file = {/Users/chaoxu/Zotero/storage/B98DLXRF/Cole - 1987 - Slowing down sorting networks to obtain faster sor.pdf}
|
||
}
|
||
|
||
@inproceedings{minimaxoptimization,
|
||
author = {Tokuyama, Takeshi},
|
||
title = {Minimax Parametric Optimization Problems and Multi-Dimensional Parametric Searching},
|
||
year = {2001},
|
||
isbn = {1581133499},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
url = {https://doi.org/10.1145/380752.380777},
|
||
doi = {10.1145/380752.380777},
|
||
abstract = {The parametric minimax problem, which finds the parameter value minimizing the weight of a solution of a combinatorial maximization problem, is a fundamental problem in sensitivity analysis. Moreover, several problems in computational geometry can be formulated as parametric minimax problems. The parametric search paradigm gives an efficient sequential algorithm for a convex parametric minimax problem with one parameter if the original non-parametric problem has an efficient parallel algorithm. We consider the parametric minimax problem with d parameters for a constant d, and solve it by using multidimensional version of the parametric search paradigm. As a new feature, we give a feasible region in the parameter space in which the parameter vector must be located.Typical results obtained as applications are: (1) Efficient solutions for some geometric problems, including theoretically efficient solutions for the minimum diameter bridging problem in d-dimensional space between convex polytopes. (2) Parametric polymatroid optimization, for example, O(n log n) time algorithm to compute the parameter vector minimizing k-largest linear parametric elements with d dimensions.},
|
||
booktitle = {Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing},
|
||
pages = {75–83},
|
||
numpages = {9},
|
||
location = {Hersonissos, Greece},
|
||
series = {STOC '01}
|
||
},
|
||
@article{Dey1998,
|
||
author = {Dey, T. K.},
|
||
title = {Improved Bounds for Planar k -Sets and Related Problems},
|
||
journal = {Discrete {\&} Computational Geometry},
|
||
year = {1998},
|
||
month = {Mar},
|
||
day = {01},
|
||
volume = {19},
|
||
number = {3},
|
||
pages = {373-382},
|
||
abstract = {We prove an O(n(k+1)1/3) upper bound for planar k -sets. This is the first considerable improvement on this bound after its early solution approximately 27 years ago. Our proof technique also applies to improve the current bounds on the combinatorial complexities of k -levels in the arrangement of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees, and parametric matroids in general.<lsiheader><onlinepub>26 June, 1998<editor>Editors-in-Chief: {\&}lsilt;a href=../edboard.html{\#}chiefs{\&}lsigt;Jacob E. Goodman, Richard Pollack{\&}lsilt;/a{\&}lsigt;<pdfname>19n3p373.pdf<pdfexist>yes<htmlexist>no<htmlfexist>no<texexist>yes<sectionname></lsiheader>},
|
||
issn = {1432-0444},
|
||
doi = {10.1007/PL00009354},
|
||
url = {https://doi.org/10.1007/PL00009354}
|
||
}
|
||
@article{Toth01,
|
||
title = {Point {{Sets}} with {{Many}} K-{{Sets}}},
|
||
author = {T{\'o}th, G.},
|
||
year = {2001},
|
||
month = jan,
|
||
journal = {Discrete \& Computational Geometry},
|
||
volume = {26},
|
||
number = {2},
|
||
pages = {187--194},
|
||
issn = {0179-5376, 1432-0444},
|
||
doi = {10.1007/s004540010022},
|
||
langid = {english}
|
||
}
|
||
@book{Schrijver2002,
|
||
address = {Berlin, Germany},
|
||
edition = {2003},
|
||
title = {Combinatorial Optimization: Polyhedra and Efficiency},
|
||
isbn = {9783540443896},
|
||
publisher = {Springer},
|
||
author = {Schrijver, Alexander},
|
||
year = {2002},
|
||
language = {en}
|
||
}
|
||
|
||
|
||
@incollection{ERDOS1973139,
|
||
title = {Chapter 13 - Dissection Graphs of Planar Point Sets},
|
||
editor = {Jagdish N. Srivastava},
|
||
booktitle = {A Survey of Combinatorial Theory},
|
||
publisher = {North-Holland},
|
||
pages = {139-149},
|
||
year = {1973},
|
||
isbn = {978-0-7204-2262-7},
|
||
doi = {https://doi.org/10.1016/B978-0-7204-2262-7.50018-1},
|
||
url = {https://www.sciencedirect.com/science/article/pii/B9780720422627500181},
|
||
author = {P. Erdös and L. Lovász and A. Simmons and E.G. Straus},
|
||
abstract = {Publisher Summary
|
||
This chapter discusses the dissection graphs of planar point sets. It discusses the general properties of the graphs Gk. The graph Gk can be constructed as follows. Let l be any oriented line containing no points of S and having k + 1 points of S on its positive side. l is to be translated to its left until it meets a point p1 of S. This line will be called l(0). Then, l(0) is to be rotated counterclockwise by θ about p1 into line l(θ) until it meets a second point p2 of S at l(θ1) = 11. l(0) is then rotated counterclockwise about p2 until l(θ) meets a point p3 of S at l(θ2) = l2, etc. This gives a sequence of points p1, p2, …, pn of S with pN+1 = p1, pN+2 = p2 and a sequence of directed lines l1, l2, l N, l N+1 with l N+2 = l1.}
|
||
}
|
||
|
||
@article{lovasz,
|
||
author = {Lovász, L.},
|
||
title = {On the number of halving lines},
|
||
journal = {Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica},
|
||
year = {1971},
|
||
volume = {14},
|
||
pages = {107-108}
|
||
}
|
||
|
||
@inbook{blelloch1990,
|
||
title = {Prefix sums and their applications},
|
||
chapter = 1,
|
||
author = {Guy E. Blelloch},
|
||
booktitle = {Synthesis of parallel algorithms},
|
||
publisher = {Morgan Kaufmann},
|
||
year = 1991,
|
||
address = {Oxford, England},
|
||
page = {35-60}
|
||
}
|
||
@article{randompoint,
|
||
issn = {00063444},
|
||
url = {http://www.jstor.org/stable/2333687},
|
||
abstract = {Various expectations concerning the convex hull of $N$ independently and identically distributed random points in the plane or in space are evaluated. Integral expressions are given for the expected area, expected perimeter, expected probability content and expected number of sides. These integrals are shown to be particularly simple when the underlying distribution is normal or uniform over a disk or sphere.},
|
||
author = {Bradley Efron},
|
||
journal = {Biometrika},
|
||
number = {3/4},
|
||
pages = {331--343},
|
||
publisher = {[Oxford University Press, Biometrika Trust]},
|
||
title = {The Convex Hull of a Random Set of Points},
|
||
urldate = {2023-01-19},
|
||
volume = {52},
|
||
year = {1965}
|
||
}
|
||
|
||
|
||
@article{vldb,
|
||
author = {Tangwongsan, Kanat and Hirzel, Martin and Schneider, Scott and Wu, Kun-Lung},
|
||
title = {General Incremental Sliding-Window Aggregation},
|
||
year = {2015},
|
||
issue_date = {February 2015},
|
||
publisher = {VLDB Endowment},
|
||
volume = {8},
|
||
number = {7},
|
||
issn = {2150-8097},
|
||
url = {https://doi.org/10.14778/2752939.2752940},
|
||
doi = {10.14778/2752939.2752940},
|
||
abstract = {Stream processing is gaining importance as more data becomes available in the form of continuous streams and companies compete to promptly extract insights from them. In such applications, sliding-window aggregation is a central operator, and incremental aggregation helps avoid the performance penalty of re-aggregating from scratch for each window change.This paper presents Reactive Aggregator (RA), a new framework for incremental sliding-window aggregation. RA is general in that it does not require aggregation functions to be invertible or commutative, and it does not require windows to be FIFO. We implemented RA as a drop-in replacement for the Aggregate operator of a commercial streaming engine. Given m updates on a window of size n, RA has an algorithmic complexity of O(m + m log (n/m)), rivaling the best prior algorithms for any m. Furthermore, RA's implementation minimizes overheads from allocation and pointer traversals by using a single flat array.},
|
||
journal = {Proc. VLDB Endow.},
|
||
month = {feb},
|
||
pages = {702–713},
|
||
numpages = {12}
|
||
}
|
||
|
||
|
||
@article{overmars_maintenance_1981,
|
||
title = {Maintenance of configurations in the plane},
|
||
volume = {23},
|
||
issn = {00220000},
|
||
url = {https://linkinghub.elsevier.com/retrieve/pii/002200008190012X},
|
||
doi = {10.1016/0022-0000(81)90012-X},
|
||
pages = {166--204},
|
||
number = {2},
|
||
journaltitle = {Journal of Computer and System Sciences},
|
||
shortjournal = {Journal of Computer and System Sciences},
|
||
author = {Overmars, Mark H. and Van Leeuwen, Jan},
|
||
urldate = {2023-05-24},
|
||
date = {1981-10},
|
||
langid = {english}
|
||
}
|
||
|
||
|
||
@inproceedings{agarwal_parametric_1998,
|
||
location = {Palo Alto, {CA}, {USA}},
|
||
title = {Parametric and kinetic minimum spanning trees},
|
||
isbn = {978-0-8186-9172-0},
|
||
url = {http://ieeexplore.ieee.org/document/743510/},
|
||
doi = {10.1109/SFCS.1998.743510},
|
||
abstract = {We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter λ and wish to compute the sequence of minimum spanning trees generated as λ varies. We also consider the kinetic minimum spanning tree problem, in which λ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n2/3 log4/3 n) per combinatorial change in the tree (or randomized O(n2/3 log n) per change). Our time bounds reduce to O(n1/2 log3/2 n) per change (O(n1/2 log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n1/4 log3/2 n) per change (O(n1/4 log n) randomized) for planar graphs with weight changes but no insertions or deletions.},
|
||
eventtitle = {39th Annual Symposium on Foundations of Computer Science},
|
||
pages = {596--605},
|
||
booktitle = {Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)},
|
||
publisher = {{IEEE} Comput. Soc},
|
||
author = {Agarwal, P.K. and Eppstein, D. and Guibas, L.J. and Henzinger, M.R.},
|
||
urldate = {2023-05-02},
|
||
date = {1998},
|
||
langid = {english},
|
||
year = {1998}
|
||
}
|
||
|
||
@article{fife_laminar_2017,
|
||
title = {Laminar matroids},
|
||
volume = {62},
|
||
issn = {01956698},
|
||
url = {https://linkinghub.elsevier.com/retrieve/pii/S0195669817300021},
|
||
doi = {10.1016/j.ejc.2017.01.002},
|
||
abstract = {A laminar family is a collection A of subsets of a set E such that, for any two intersecting sets, one is contained in the other. For a capacity function c on A, let I be \{I : {\textbar}I ∩ A{\textbar} ≤ c(A) for all A ∈ A\}. Then I is the collection of independent sets of a (laminar) matroid on E. We present a method of compacting laminar presentations, characterize the class of laminar matroids by their excluded minors, present a way to construct all laminar matroids using basic operations, and compare the class of laminar matroids to other well-known classes of matroids.},
|
||
pages = {206--216},
|
||
journal = {European Journal of Combinatorics},
|
||
journaltitle = {European Journal of Combinatorics},
|
||
shortjournal = {European Journal of Combinatorics},
|
||
author = {Fife, Tara and Oxley, James},
|
||
urldate = {2023-05-04},
|
||
date = {2017-05},
|
||
langid = {english},
|
||
year = {2017}
|
||
}
|
||
|
||
|
||
@inproceedings{heavypathdecomposition,
|
||
author = {Sleator, Daniel D. and Tarjan, Robert Endre},
|
||
title = {A Data Structure for Dynamic Trees},
|
||
year = {1981},
|
||
isbn = {9781450373920},
|
||
publisher = {Association for Computing Machinery},
|
||
address = {New York, NY, USA},
|
||
url = {https://doi.org/10.1145/800076.802464},
|
||
doi = {10.1145/800076.802464},
|
||
abstract = {We propose a data structure to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Our data structure requires O(log n) time per operation when the time is amortized over a sequence of operations. Using our data structure, we obtain new fast algorithms for the following problems:(1) Computing deepest common ancestors.(2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows.(3) Computing certain kinds of constrained minimum spanning trees.(4) Implementing the network simplex algorithm for the transshipment problem.Our most significant application is (2); we obtain an O(mn log n)-time algorithm to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs.},
|
||
booktitle = {Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing},
|
||
pages = {114–122},
|
||
numpages = {9},
|
||
location = {Milwaukee, Wisconsin, USA},
|
||
series = {STOC '81}
|
||
}
|
||
|
||
@article{Edmonds1971,
|
||
author={Edmonds, Jack},
|
||
title={Matroids and the greedy algorithm},
|
||
journal={Mathematical Programming},
|
||
year={1971},
|
||
month={Dec},
|
||
day={01},
|
||
volume={1},
|
||
number={1},
|
||
pages={127-136},
|
||
abstract={Linear-algebra rank is the solution to an especially tractable optimization problem. This tractability is viewed abstractly, and extended to certain more general optimization problems which are linear programs relative to certain derived polyhedra.},
|
||
issn={1436-4646},
|
||
doi={10.1007/BF01584082},
|
||
url={https://doi.org/10.1007/BF01584082}
|
||
}
|
||
|
||
|
||
@misc{enwiki_envelope,
|
||
author = "{Wikipedia contributors}",
|
||
title = "Lower envelope --- {Wikipedia}{,} The Free Encyclopedia",
|
||
year = "2021",
|
||
howpublished = "\url{https://en.wikipedia.org/w/index.php?title=Lower_envelope&oldid=1024815458}",
|
||
note = "[Online; accessed 20-May-2024]"
|
||
}
|
||
|
||
@article{daskalakis_how_nodate,
|
||
title = {How good is the {Chord} algorithm?},
|
||
abstract = {The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics. We analyze the performance of the chord algorithm, as compared to the optimal approximation that achieves a desired accuracy with the minimum number of points. We prove sharp upper and lower bounds, both in the worst case and average case setting.},
|
||
language = {en},
|
||
author = {Daskalakis, Constantinos and Diakonikolas, Ilias and Yannakakis, Mihalis},
|
||
file = {1309.7084v1:/Users/congyu/Zotero/storage/9M85GJGA/1309.7084v1.pdf:application/pdf;PDF:/Users/congyu/Zotero/storage/2EUWCRCA/Daskalakis et al. - How good is the Chord algorithm.pdf:application/pdf},
|
||
}
|
||
|
||
|
||
@article{eisner_mathematical_1976,
|
||
title = {Mathematical {Techniques} for {Efficient} {Record} {Segmentation} in {Large} {Shared} {Databases}},
|
||
volume = {23},
|
||
issn = {0004-5411, 1557-735X},
|
||
url = {https://dl.acm.org/doi/10.1145/321978.321982},
|
||
doi = {10.1145/321978.321982},
|
||
abstract = {It is possible to significantly reduce the average cost of information retrieval from a large shared database by partitioning data items stored within each record into a primary and a secondary record segment. An analytic model, based upon knowledge of data item lengths, transportation costs, and retrieval patterns, is developed to assist an analyst with this assignment problem. The model is generally applicable to environments in which a database resides in secondary storage, and is useful for both uniprogramming and multiprogramming systems. A computationally tractable record design algorithm has been implemented as a Fortran program and applied to numerous problems. Realistic examples are presented which demonstrate a potential for reducing total system cost by more than 65 percent.},
|
||
language = {en},
|
||
number = {4},
|
||
urldate = {2024-09-26},
|
||
journal = {Journal of the ACM},
|
||
author = {Eisner, Mark J. and Severance, Dennis G.},
|
||
month = oct,
|
||
year = {1976},
|
||
pages = {619--635},
|
||
file = {PDF:/Users/congyu/Zotero/storage/Y7ILXXL9/Eisner and Severance - 1976 - Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases.pdf:application/pdf},
|
||
}
|
||
|
||
@article{lust_multiobjective_2012,
|
||
title = {The multiobjective multidimensional knapsack problem: a survey and a new approach},
|
||
volume = {19},
|
||
issn = {0969-6016, 1475-3995},
|
||
shorttitle = {The multiobjective multidimensional knapsack problem},
|
||
url = {https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2011.00840.x},
|
||
doi = {10.1111/j.1475-3995.2011.00840.x},
|
||
abstract = {The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or to approximate the set of efficient solutions. In a first step, we classify and describe briefly the existing works, that are essentially based on the use of metaheuristics. In a second step, we propose the adaptation of the twophase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very-large scale neighborhood (VLSN) in the second phase of the method, that is the Pareto local search. We compare our results to state-of-the-art results and we show that we obtain results never reached before by heuristics, for the biobjective instances. Finally we consider the extension to three-objective instances.},
|
||
language = {en},
|
||
number = {4},
|
||
urldate = {2024-09-29},
|
||
journal = {International Transactions in Operational Research},
|
||
author = {Lust, Thibaut and Teghem, Jacques},
|
||
month = jul,
|
||
year = {2012},
|
||
pages = {495--520},
|
||
file = {PDF:/Users/congyu/Zotero/storage/X5N6KIUT/Lust and Teghem - 2012 - The multiobjective multidimensional knapsack problem a survey and a new approach.pdf:application/pdf},
|
||
}
|
||
|
||
|
||
@article{calinescu_maximizing_2011,
|
||
title = {Maximizing a {Monotone} {Submodular} {Function} {Subject} to a {Matroid} {Constraint}},
|
||
volume = {40},
|
||
issn = {0097-5397, 1095-7111},
|
||
url = {http://epubs.siam.org/doi/10.1137/080733991},
|
||
doi = {10.1137/080733991},
|
||
abstract = {Let f : 2X → R+ be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem maxS∈I f (S). It is known that the greedy algorithm yields a 1/2approximation [17] for this problem. For certain special cases, e.g. max{\textbar}S{\textbar}≤k f (S), the greedy algorithm yields a (1 − 1/e)-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning f (S) for a given set S) [37], and also for explicitly posed instances assuming P = N P [13].},
|
||
language = {en},
|
||
number = {6},
|
||
urldate = {2024-08-01},
|
||
journal = {SIAM Journal on Computing},
|
||
author = {Calinescu, Gruia and Chekuri, Chandra and Pál, Martin and Vondrák, Jan},
|
||
month = jan,
|
||
year = {2011},
|
||
pages = {1740--1766},
|
||
file = {Calinescu et al. - 2011 - Maximizing a Monotone Submodular Function Subject .pdf:/Users/congyu/Zotero/storage/YX9EQ3UB/Calinescu et al. - 2011 - Maximizing a Monotone Submodular Function Subject .pdf:application/pdf},
|
||
}
|
||
|
||
|
||
@article{lee_maximizing_2010,
|
||
title = {Maximizing {Nonmonotone} {Submodular} {Functions} under {Matroid} or {Knapsack} {Constraints}},
|
||
volume = {23},
|
||
issn = {0895-4801},
|
||
url = {https://epubs.siam.org/doi/10.1137/090750020},
|
||
doi = {10.1137/090750020},
|
||
abstract = {Let \$f:2{\textasciicircum}X {\textbackslash}rightarrow {\textbackslash}cal R\_+\$ be a monotone submodular set function, and let \$(X,{\textbackslash}cal I)\$ be a matroid. We consider the problem \$\{{\textbackslash}rm max\}\_\{S {\textbackslash}in {\textbackslash}cal I\} f(S)\$. It is known that the greedy algorithm yields a \$1/2\$-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73–87] for this problem. For certain special cases, e.g., \$\{{\textbackslash}rm max\}\_\{{\textbar}S{\textbar} {\textbackslash}leq k\} f(S)\$, the greedy algorithm yields a \$(1-1/e)\$-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning \$f(S)\$ for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177–188] and for explicitly posed instances assuming \$P {\textbackslash}neq NP\$ [U. Feige, J. ACM, 45 (1998), pp. 634–652]. In this paper, we provide a randomized \$(1-1/e)\$-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307–328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrák, Proceedings of the \$38\$th ACM Symposium on Theory of Computing, 2008, pp. 67–74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires \${\textbar}X{\textbar}\$ to be exponential in the original problem size, we are able to achieve a \$(1-1/e-o(1))\$-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.},
|
||
number = {4},
|
||
urldate = {2024-09-29},
|
||
journal = {SIAM Journal on Discrete Mathematics},
|
||
author = {Lee, Jon and Mirrokni, Vahab S. and Nagarajan, Viswanath and Sviridenko, Maxim},
|
||
month = jan,
|
||
year = {2010},
|
||
note = {Publisher: Society for Industrial and Applied Mathematics},
|
||
pages = {2053--2078},
|
||
file = {PDF:/Users/congyu/Zotero/storage/LZ2EKEKW/Lee et al. - 2010 - Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints.pdf:application/pdf},
|
||
}
|
||
|
||
@misc{sviridenko_optimal_2014,
|
||
title = {Optimal approximation for submodular and supermodular optimization with bounded curvature},
|
||
url = {http://arxiv.org/abs/1311.4728},
|
||
abstract = {We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1 − c/e)-approximation — the first improvement over the greedy (1 − e−c)/c-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint.},
|
||
language = {en},
|
||
urldate = {2024-10-25},
|
||
publisher = {arXiv},
|
||
author = {Sviridenko, Maxim and Vondrák, Jan and Ward, Justin},
|
||
month = dec,
|
||
year = {2014},
|
||
note = {arXiv:1311.4728 [cs]},
|
||
keywords = {Computer Science - Data Structures and Algorithms},
|
||
file = {PDF:/Users/congyu/Zotero/storage/LS7Y3DYF/Sviridenko et al. - 2014 - Optimal approximation for submodular and supermodular optimization with bounded curvature.pdf:application/pdf},
|
||
}
|
||
@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.56,
|
||
author = {Doron-Arad, Ilan and Kulik, Ariel and Shachnai, Hadas},
|
||
title = {{Lower Bounds for Matroid Optimization Problems with a Linear Constraint}},
|
||
booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
|
||
pages = {56:1--56:20},
|
||
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
|
||
ISBN = {978-3-95977-322-5},
|
||
ISSN = {1868-8969},
|
||
year = {2024},
|
||
volume = {297},
|
||
editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
|
||
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
|
||
address = {Dagstuhl, Germany},
|
||
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.56},
|
||
URN = {urn:nbn:de:0030-drops-201990},
|
||
doi = {10.4230/LIPIcs.ICALP.2024.56},
|
||
annote = {Keywords: matroid optimization, budgeted problems, knapsack, approximation schemes}
|
||
} |