-
Notifications
You must be signed in to change notification settings - Fork 0
/
reference.bib
178 lines (169 loc) · 12.1 KB
/
reference.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
@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},
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},
}
@inproceedings{Clarkson_1988, address={Urbana-Champaign, Illinois, United States}, title={Applications of random sampling in computational geometry, II}, ISBN={9780897912709}, url={http://portal.acm.org/citation.cfm?doid=73393.73394}, DOI={10.1145/73393.73394}, booktitle={Proceedings of the fourth annual symposium on Computational geometry - SCG ’88}, publisher={ACM Press}, author={Clarkson, K. L.}, year={1988}, pages={1–11}, language={en} }
@article{Tarela_Alonso_Martínez_1990, title={A representation method for PWL functions oriented to parallel processing}, volume={13}, rights={https://www.elsevier.com/tdm/userlicense/1.0/}, ISSN={0895-7177}, url={https://linkinghub.elsevier.com/retrieve/pii/089571779090090A}, DOI={10.1016/0895-7177(90)90090-a}, number={10}, journal={Mathematical and Computer Modelling}, author={Tarela, J.M. and Alonso, E. and Martínez, M.V.}, year={1990}, pages={75–83}, language={en} }
@article{Toriello_Vielma_2012, title={Fitting piecewise linear continuous functions}, volume={219}, rights={https://www.elsevier.com/tdm/userlicense/1.0/}, ISSN={0377-2217}, url={https://linkinghub.elsevier.com/retrieve/pii/S0377221711011246}, DOI={10.1016/j.ejor.2011.12.030}, number={1}, journal={European Journal of Operational Research}, author={Toriello, Alejandro and Vielma, Juan Pablo}, year={2012}, month=may, pages={86–95}, language={en} }
@book{boyd_convex_2004,
address = {Cambridge, UK ; New York},
title = {Convex optimization},
isbn = {978-0-521-83378-3},
language = {en},
publisher = {Cambridge University Press},
author = {Boyd, Stephen P. and Vandenberghe, Lieven},
year = {2004},
keywords = {Mathematical optimization, Convex functions},
file = {Boyd and Vandenberghe - 2004 - Convex optimization.pdf:/Users/congyu/Zotero/storage/NDN385HW/Boyd and Vandenberghe - 2004 - Convex optimization.pdf:application/pdf},
}
@phdthesis{mountford_minkowski_nodate,
title = {Minkowski {Sums} of {Polytopes}: {Combinatorics} and {Computation}},
language = {en},
author = {Mountford, T and Liebling, T and Fukuda, K and Gritzmann, P and Ziegler, G},
file = {Mountford et al. - accept´ee sur proposition du jury .pdf:/Users/congyu/Zotero/storage/HMXNTH7B/Mountford et al. - accept´ee sur proposition du jury .pdf:application/pdf},
}
@article{cardon_partitioning_1982,
title = {Partitioning a graph in {O}({AlogV})},
volume = {19},
issn = {0304-3975},
url = {https://www.sciencedirect.com/science/article/pii/0304397582900160},
doi = {10.1016/0304-3975(82)90016-0},
abstract = {We present an O(¦A¦log2¦V¦) algorithm to partition a graph, where V is the set of vertices and A the set of arcs, extending Hopcroft's fast partitioning algorithm.},
number = {1},
urldate = {2024-10-09},
journal = {Theoretical Computer Science},
author = {Cardon, A. and Crochemore, M.},
month = jul,
year = {1982},
pages = {85--98},
}
@inproceedings{grohe_dimension_2014,
address = {Berlin, Heidelberg},
title = {Dimension {Reduction} via {Colour} {Refinement}},
isbn = {978-3-662-44777-2},
abstract = {Colour refinement is a basic algorithmic routine for graph isomorphism testing, appearing as a subroutine in almost all practical isomorphism solvers. It partitions the vertices of a graph into “colour classes” in such a way that all vertices in the same colour class have the same number of neighbours in every colour class. There is a tight correspondence between colour refinement and fractional isomorphisms of graphs, which are solutions to the LP relaxation of a natural ILP formulation of graph isomorphism.},
booktitle = {Algorithms - {ESA} 2014},
publisher = {Springer Berlin Heidelberg},
author = {Grohe, Martin and Kersting, Kristian and Mladenov, Martin and Selman, Erkal},
editor = {Schulz, Andreas S. and Wagner, Dorothea},
year = {2014},
pages = {505--516},
file = {arxiv:/Users/congyu/Zotero/storage/8FBZLD8K/Grohe et al. - Dimension Reduction via Colour Refinement.pdf:application/pdf;esa colour refinement:/Users/congyu/Zotero/storage/HC4NWELG/esa colour refinement.pdf:application/pdf},
}
@article{chan_improved_nodate,
author = {Chan, Timothy M.},
title = {Improved Deterministic Algorithms for Linear Programming in Low Dimensions},
year = {2018},
issue_date = {July 2018},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {14},
number = {3},
issn = {1549-6325},
url = {https://doi.org/10.1145/3155312},
doi = {10.1145/3155312},
abstract = {Chazelle and Matou\v{s}ek [J. Algorithms, 1996] presented a derandomization of Clarkson’s sampling-based algorithm [J. ACM, 1995] for solving linear programs with n constraints and d variables in d(7+o(1))dn deterministic time. The time bound can be improved to d(5+o(1))dn with subsequent work by Br\"{o}nnimann, Chazelle, and Matou\v{s}ek [SIAM J. Comput., 1999]. We first point out a much simpler derandomization of Clarkson’s algorithm that avoids ε-approximations and runs in d(3+o(1))dn time. We then describe a few additional ideas that eventually improve the deterministic time bound to d(1/2+o(1))dn.},
journal = {ACM Trans. Algorithms},
month = jun,
articleno = {30},
numpages = {10},
keywords = {linear programming, epsilon-nets, derandomization, Computational geometry}
}
@article{paige_three_1987,
title = {Three {Partition} {Refinement} {Algorithms}},
volume = {16},
issn = {0097-5397},
url = {https://epubs.siam.org/doi/10.1137/0216062},
doi = {10.1137/0216062},
abstract = {PROPORTION EXTEND SORT is a new sorting algorithm, the basic principle of which is similar to PROPORTION SPLIT SORT. This algorithm sorts a sequence by constructing three subproblems, using a QuickSort-like pivot technique and solving recursively each subproblem. The original problem and three subproblems all are of such a structure: a sorted subsequence followed by an unsorted subsequence. The size of the original problem always equals the size of the third subproblem, but in general, the sorted subsequence of the third subproblem is p+1 times as much as the sorted subsequence of the original, where p is a fixed positive constant. The worst case number of comparisons required by this algorithm is less than 1/log (1+1/(2p2 +2p-1))nlog n for \$p {\textbackslash}geq 1\$. Empirical results show that the average number of comparisons is close to n log n-O(n) for some p. From our experiments for sorting integers, when p = 16, this algorithm is yet faster, on average, than PROPORTION SPLIT SORT which is faster than CLEVER QUICKSORT.},
number = {6},
urldate = {2024-10-18},
journal = {SIAM Journal on Computing},
author = {Paige, Robert and Tarjan, Robert E.},
month = dec,
year = {1987},
note = {Publisher: Society for Industrial and Applied Mathematics},
pages = {973--989},
file = {PDF:/Users/congyu/Zotero/storage/ABBDRPYP/Paige and Tarjan - 1987 - Three Partition Refinement Algorithms.pdf:application/pdf},
}
@article{berkholz_tightbound_2017,
author = {Berkholz, Christoph and Bonsma, Paul and Grohe, Martin},
title = {Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement},
year = {2017},
issue_date = {May 2017},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {60},
number = {4},
issn = {1432-4350},
url = {https://doi.org/10.1007/s00224-016-9686-0},
doi = {10.1007/s00224-016-9686-0},
abstract = {An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is a widely used subroutine for graph isomorphism testing algorithms, since any automorphism needs to be colour preserving. We give an O((m + n)log n) algorithm for finding a canonical version of such a stable colouring, on graphs with n vertices and m edges. We show that no faster algorithm is possible, under some modest assumptions about the type of algorithm, which captures all known colour refinement algorithms.},
journal = {Theor. Comp. Sys.},
month = may,
pages = {581–614},
numpages = {34},
keywords = {Canonical labelling, Colour refinement, Graph isomorphism, Partition refinement}
}
@InProceedings{kiefer_et_alicalp20,
author = {Kiefer, Sandra and McKay, Brendan D.},
title = {{The Iteration Number of Colour Refinement}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {73:1--73:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.73},
URN = {urn:nbn:de:0030-drops-124801},
doi = {10.4230/LIPIcs.ICALP.2020.73},
annote = {Keywords: Colour Refinement, iteration number, Weisfeiler-Leman algorithm, quantifier depth}
}
@article{dyer_multidimensional_1986,
title = {On a {Multidimensional} {Search} {Technique} and {Its} {Application} to the {Euclidean} {One}-{Centre} {Problem}},
volume = {15},
issn = {0097-5397, 1095-7111},
url = {http://epubs.siam.org/doi/10.1137/0215052},
doi = {10.1137/0215052},
abstract = {The paper is divided into two main sections. The first deals with a multidimensional search technique of Megiddo [J. Assoc. Comput. Mach., 31 (.1984), pp. 114-127], and suggests an improvement. The second gives an application of the technique to the Euclidean one-centre problem in a. An algorithm of time-complexity O(3{\textless}d+2)2n) is derived for this problem. This improves the best previous bound even in the case d 2.},
language = {en},
number = {3},
urldate = {2024-10-23},
journal = {SIAM Journal on Computing},
author = {Dyer, M. E.},
month = aug,
year = {1986},
pages = {725--738},
file = {PDF:/Users/congyu/Zotero/storage/7GR38HRX/Dyer - 1986 - On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem.pdf:application/pdf},
}
@article{das_linear_2020,
title = {Linear time algorithms for {Euclidean} 1-center in ℜ d with non-linear convex constraints},
volume = {280},
issn = {0166218X},
url = {https://linkinghub.elsevier.com/retrieve/pii/S0166218X19304329},
doi = {10.1016/j.dam.2019.09.009},
abstract = {In this paper, we first present a linear-time algorithm to find the smallest circle enclosing n given points in ℜ2 with the constraint that the center of the smallest enclosing circle lies inside a given disk. We extend this result to ℜ3 by computing constrained smallest enclosing sphere centered on a given sphere. We generalize the result for the case of points in ℜd where the center of the minimum enclosing ball lies inside a given ball. We show that similar problem of computing minimum intersecting/stabbing ball for a set of hyper planes in ℜd can also be solved using similar techniques. We also show how the minimum intersecting disk with the center constrained on a given disk can be computed to intersect a set of convex polygons. Lastly, we show that this technique is applicable when the center of minimum enclosing/intersecting ball lies in a convex region bounded by constant number of non-linear constraints with computability assumptions. We solve each of these problems in linear time in input size for fixed dimension.},
language = {en},
urldate = {2024-10-26},
journal = {Discrete Applied Mathematics},
author = {Das, Sandip and Nandy, Ayan and Sarvottamananda, Swami},
month = jun,
year = {2020},
pages = {71--85},
file = {PDF:/Users/congyu/Zotero/storage/C5RBHRJJ/Das et al. - 2020 - Linear time algorithms for Euclidean 1-center in ℜ d with non-linear convex constraints.pdf:application/pdf},
}