×

The complexity of controlled selection. (English) Zbl 0800.68496


MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Broder, A., Generating random spanning trees, (Proceedings, 30th IEEE Symposium on Foundations of Computer Science (1989))
[2] Caratheodory, C., Uber den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen, Math. Ann., 64, 95-115 (1907) · JFM 38.0448.01
[3] Causey, B.; Cox, L.; Ernst, L., Application of transportation theory to statistical problems, J. Amer. Statist. Assoc., 80, 903-909 (1985)
[4] Colbourn, C.; Day, R.; Nel, L., Ranking and unranking spanning trees, J. Algorithms, 10, 271-284 (1989) · Zbl 0681.68087
[5] Cox, L., A constructive procedure for unbiased controlled rounding, J. Amer. Statist. Assoc., 82, 520-524 (1988) · Zbl 0656.62071
[6] Cunningham, W., Minimum cuts, modular functions, and matroid polyhedra, Networks, 15, 205-215 (1985) · Zbl 0581.90059
[7] Gabow, H.; Westermann, H., Forests, frames, and games: Algorithms for matroid sums and applications, (Proceedings, 20th ACM Symposium on Theory of Computation (1988)), 407-421 · Zbl 0771.05026
[8] Garey, M.; Johnson, D., (Computers and Intractability, A Guide to NP-Completeness (1979), Freeman: Freeman New York) · Zbl 0411.68039
[9] Goodman, R.; Kish, L., Controlld selection—A technique in probability sampling, J. Amer. Statist. Assoc., 45, 350-372 (1950)
[10] Grollman, J.; Selman, A., Complexity measures for public-key cryptosystems, (Proceedings, 27th IEEE Symposium on Foundations of Computer Science (1984)), 495-503
[11] Grotschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981), Corrigendum; Combinatorica, 4, 291-295 · Zbl 0492.90056
[12] Hoyler, I., The NP-completeness of edge coloring, SIAM J. Comput., 10, 718-720 (1981) · Zbl 0473.68034
[13] Jerrum, M.; Valiant, L.; Vazirani, V., Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci., 43, 169-188 (1986) · Zbl 0597.68056
[14] Karp, R., Reducibility among combinatorial problems, (Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-104 · Zbl 0366.68041
[15] Khachiyan, L., A polynomial time algorithm in linear programming, Soviet Math. Dokl., 20, 191-194 (1979) · Zbl 0409.90079
[16] Konijn, H., (Statistical Theory of Sample Survey Design and Analysis (1973), North-Holland: North-Holland Amsterdam) · Zbl 0296.62008
[17] Lawler, E., (Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart, Winston: Holt, Rinehart, Winston New York) · Zbl 0413.90040
[18] Lovász, L., (An Algorithmic Theory of Numbers, Graphs and Convexity, Vol. 50 (1986), SIAM: SIAM Philadelphia), CMBS · Zbl 0606.68039
[19] Papadimitriou, C.; Yannakakis, M., The complexity of facets (and some facets of complexity, J. Comput. System Sci., 28, 244-259 (1982) · Zbl 0571.68028
[20] Picard, J.; Queyranne, M., Selected applications of minimum cuts in networks, Infor, 20, 394-422 (1982) · Zbl 0501.90069
[21] Pruhs, K., The computational complexity of some rounding and survey overlap problems, (Proceedings, Survey Methods Section of the American Statistical Association (1989))
[22] Pruhs, K., The complexity of Controlled Selection, (Ph. D. thesis (1989), University of Wisconsin-Madison) · Zbl 0800.68496
[23] Raghavan, P., Probabilistic construction of deterministic algorithms: Approximating packing integer programs, J. Comput. System Sci., 37, 130-143 (1988) · Zbl 0659.90066
[24] Raghavan, P.; Thompson, D., Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 4, 365-374 (1987) · Zbl 0651.90052
[25] Tanenbaum, A., (Computer Networks (1981), Prentice-Hall: Prentice-Hall Englewood, NJ)
[26] Tutte, W., On the problem of decomposing a graph into connected components, J. London Math. Soc., 36, 221-230 (1961) · Zbl 0096.38001
[27] Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, 410-421 (1979) · Zbl 0419.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.