The DOI matches its Crossref record.
Theory of Linear and Integer Programming
Abstract
Introduction and Preliminaries. Problems, Algorithms, and Complexity. LINEAR ALGEBRA. Linear Algebra and Complexity. LATTICES AND LINEAR DIOPHANTINE EQUATIONS. Theory of Lattices and Linear Diophantine Equations. Algorithms for Linear Diophantine Equations. Diophantine Approximation and Basis Reduction. POLYHEDRA, LINEAR INEQUALITIES, AND LINEAR PROGRAMMING. Fundamental Concepts and Results on Polyhedra, Linear Inequalities, and Linear Programming. The Structure of Polyhedra. Polarity, and Blocking and Anti--Blocking Polyhedra. Sizes and the Theoretical Complexity of Linear Inequalities and Linear Programming. The Simplex Method. Primal--Dual, Elimination, and Relaxation Methods. Khachiyana s Method for Linear Programming. The Ellipsoid Method for Polyhedra More Generally. Further Polynomiality Results in Linear Programming. INTEGER LINEAR PROGRAMMING. Introduction to Integer Linear Programming. Estimates in Integer Linear Programming. The Complexity of Integer Linear Programming. Totally Unimodular Matrices: Fundamental Properties and Examples. Recognizing Total Unimodularity. Further Theory Related to Total Unimodularity. Integral Polyhedra and Total Dual Integrality. Cutting Planes. Further Methods in Integer Linear Programming. References. Indexes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Reinforcement Learning: A Survey
Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.301 · Cited by 8,972
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Planning and acting in partially observable stochastic domains
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00023-x · Cited by 4,149
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems
del Valle, Y., Venayagamoorthy, G. K., Mohagheghi, S., Hernandez, J.-C., & Harley, R. G. (2008) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2007.896686 · Cited by 2,277
Network Function Virtualization: State-of-the-Art and Research Challenges
Mijumbi, R., Serrat, J., Gorricho, J.-L., Bouten, N., De Turck, F., & Boutaba, R. (2016) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2015.2477041 · Cited by 1,933
Invitation to Fixed-Parameter Algorithms
Niedermeier, R. (2006) · doi:10.1093/acprof:oso/9780198566076.001.0001 · Cited by 1,668
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
A data locality optimizing algorithm
Wolf, M. E., & Lam, M. S. (1991) · Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation - PLDI '91 · doi:10.1145/113445.113449 · Cited by 1,331
Mathematical problems for the next century
Smale, S. (1998) · The Mathematical Intelligencer · doi:10.1007/bf03025291 · Cited by 1,217
Satisfiability Modulo Theories
Barrett, C., & Tinelli, C. (2018) · Handbook of Model Checking · doi:10.1007/978-3-319-10575-8_11 · Cited by 1,122
Integer and combinatorial optimization
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)91259-2 · Cited by 1,117
Selected Topics in Column Generation
Lübbecke, M. E., & Desrosiers, J. (2005) · Operations Research · doi:10.1287/opre.1050.0234 · Cited by 1,102
Efficient encoding of low-density parity-check codes
Richardson, T. J., & Urbanke, R. L. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910579 · Cited by 1,028
Computationally Manageable Combinational Auctions
Rothkopf, M. H., Pekeč, A., & Harstad, R. M. (1998) · Management Science · doi:10.1287/mnsc.44.8.1131 · Cited by 1,024
Some NP-complete problems in quadratic and nonlinear programming
Murty, K. G., & Kabadi, S. N. (1987) · Mathematical Programming · doi:10.1007/bf02592948 · Cited by 1,003
Combinatorial Auctions: A Survey
de Vries, S., & Vohra, R. V. (2003) · INFORMS Journal on Computing · doi:10.1287/ijoc.15.3.284.16077 · Cited by 985
Ultra-Dense Networks: A Survey
Kamel, M., Hamouda, W., & Youssef, A. (2016) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2016.2571730 · Cited by 919
A practical automatic polyhedral parallelizer and locality optimizer
Bondhugula, U., Hartono, A., Ramanujam, J., & Sadayappan, P. (2008) · Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1375581.1375595 · Cited by 880
Virtual Network Embedding with Coordinated Node and Link Mapping
Chowdhury, N. M. M. K., Rahman, M. R., & Boutaba, R. (2009) · IEEE INFOCOM 2009 · doi:10.1109/infcom.2009.5061987 · Cited by 823
ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping
Chowdhury, M., Rahman, M. R., & Boutaba, R. (2012) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2011.2159308 · Cited by 818
Nieuwenhuis, R., Oliveras, A., & Tinelli, C. (2006) · Journal of the ACM · doi:10.1145/1217856.1217859 · Cited by 783
OptiType: precision HLA typing from next-generation sequencing data
Szolek, A., Schubert, B., Mohr, C., Sturm, M., Feldhahn, M., & Kohlbacher, O. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu548 · Cited by 769
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 753
A survey of computational complexity results in systems and control
Blondel, V. D., & Tsitsiklis, J. N. (2000) · Automatica · doi:10.1016/s0005-1098(00)00050-9 · Cited by 732
Mixed-integer nonlinear optimization
Belotti, P., Kirches, C., Leyffer, S., Linderoth, J., Luedtke, J., & Mahajan, A. (2013) · Acta Numerica · doi:10.1017/s0962492913000032 · Cited by 712
Interior Methods for Nonlinear Optimization
Forsgren, A., Gill, P. E., & Wright, M. H. (2002) · SIAM Review · doi:10.1137/s0036144502414942 · Cited by 699
Information Theoretic Security
Liang, Y., Poor, H. V., & Shamai (Shitz), S. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601982414 · Cited by 686
Sums of Squares, Moment Matrices and Optimization Over Polynomials
Laurent, M. (2009) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-0-387-09686-5_7 · Cited by 648
Algebraic algorithms for sampling from conditional distributions
Diaconis, P., & Sturmfels, B. (1998) · The Annals of Statistics · doi:10.1214/aos/1030563990 · Cited by 616
A logic for reasoning about probabilities
Fagin, R., Halpern, J. Y., & Megiddo, N. (1990) · Information and Computation · doi:10.1016/0890-5401(90)90060-u · Cited by 584
Using Linear Programming to Decode Binary Linear Codes
Feldman, J., Wainwright, M. J., & Karger, D. R. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.842696 · Cited by 572
Irigoin, F., & Triolet, R. (1988) · Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '88 · doi:10.1145/73560.73588 · Cited by 564
Some efficient solutions to the affine scheduling problem. I. One-dimensional time
Feautrier, P. (1992) · International Journal of Parallel Programming · doi:10.1007/bf01407835 · Cited by 555
The CLP( ℛ ) language and system
Jaffar, J., Michaylov, S., Stuckey, P. J., & Yap, R. H. C. (1992) · ACM Transactions on Programming Languages and Systems · doi:10.1145/129393.129398 · Cited by 521
Generation of fiducial marker dictionaries using Mixed Integer Linear Programming
Garrido-Jurado, S., Muñoz-Salinas, R., Madrid-Cuevas, F. J., & Medina-Carnicer, R. (2016) · Pattern Recognition · doi:10.1016/j.patcog.2015.09.023 · Cited by 490
Code generation in the polyhedral model is easier than you think
Bastoul, C. (2004) · Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques, 2004. PACT 2004. · doi:10.1109/pact.2004.1342537 · Cited by 447
On the Complexity of Solving Markov Decision Problems
Littman, M. L., Dean, T., & Kaelbling, L. P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.4971 · Cited by 424
Robust constraint satisfaction: invariant sets and predictive control
Kerrigan, E. C. (2000) · doi:10.25561/4346 · Cited by 376
Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time
Feautrier, P. (1992) · International Journal of Parallel Programming · doi:10.1007/bf01379404 · Cited by 368
Learning on the border: active learning in imbalanced data classification
Ertekin, S., Huang, J., Bottou, L., & Giles, L. (2007) · Proceedings of the sixteenth ACM conference on Conference on information and knowledge management · doi:10.1145/1321440.1321461 · Cited by 365
Desrosiers, J., & Lübbecke, M. E. (2006) · Column Generation · doi:10.1007/0-387-25486-2_1 · Cited by 363
Mixed Integer Linear Programming Formulation Techniques
Vielma, J. P. (2015) · SIAM Review · doi:10.1137/130915303 · Cited by 358
Linear Invariant Generation Using Non-linear Constraint Solving
Colón, M. A., Sankaranarayanan, S., & Sipma, H. B. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45069-6_39 · Cited by 351
Portfolio optimization with linear and fixed transaction costs
Lobo, M. S., Fazel, M., & Boyd, S. (2007) · Annals of Operations Research · doi:10.1007/s10479-006-0145-1 · Cited by 350
Wright, M. (2004) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-04-01040-7 · Cited by 345
Path-Following Methods for Linear Programming
Gonzaga, C. C. (1992) · SIAM Review · doi:10.1137/1034048 · Cited by 341
The Economics of Input-Output Analysis
ten Raa, T. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511610783 · Cited by 321
Scanning polyhedra with DO loops
Ancourt, C., & Irigoin, F. (1991) · Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/109625.109631 · Cited by 315
Sense and avoid technologies with applications to unmanned aircraft systems: Review and prospects
Yu, X., & Zhang, Y. (2015) · Progress in Aerospace Sciences · doi:10.1016/j.paerosci.2015.01.001 · Cited by 301
Potential Function Methods for Approximately Solving Linear Programming Problems
(2002) · International Series in Operations Research & Management Science · doi:10.1007/b115460 · Cited by 291
A Fixed-Point Approach to Stable Matchings and Some Applications
Fleiner, T. (2003) · Mathematics of Operations Research · doi:10.1287/moor.28.1.103.14256 · Cited by 291
Fragouli, C., & Soljanin, E. (2006) · now publishers, Inc. eBooks · doi:10.1561/9781601980335 · Cited by 288
Multi-robot coalition formation
Vig, L., & Adams, J. A. (2006) · IEEE Transactions on Robotics · doi:10.1109/tro.2006.878948 · Cited by 275
Rounding of Polytopes in the Real Number Model of Computation
Khachiyan, L. G. (1996) · Mathematics of Operations Research · doi:10.1287/moor.21.2.307 · Cited by 273
A Survey on Task Offloading in Multi-access Edge Computing
Islam, A., Debnath, A., Ghose, M., & Chakraborty, S. (2021) · Journal of Systems Architecture · doi:10.1016/j.sysarc.2021.102225 · Cited by 271
Avery, C., Resnick, P., & Zeckhauser, R. (1999) · American Economic Review · doi:10.1257/aer.89.3.564 · Cited by 267
Cloud service selection: State-of-the-art and future research directions
Sun, L., Dong, H., Hussain, F. K., Hussain, O. K., & Chang, E. (2014) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2014.07.019 · Cited by 263
Effective lattice point counting in rational convex polytopes
De Loera, J. A., Hemmecke, R., Tauzer, J., & Yoshida, R. (2004) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2003.04.003 · Cited by 261
An integer linear programming approach for finding deregulated subgraphs in regulatory networks
Backes, C., Rurainski, A., Klau, G. W., Müller, O., Stöckel, D., Gerasch, A., Küntzer, J., Maisel, D., Ludwig, N., Hein, M., et al. (2012) · Nucleic Acids Research · doi:10.1093/nar/gkr1227 · Cited by 259
Object Detection and Tracking for Autonomous Navigation in Dynamic Environments
Ess, A., Schindler, K., Leibe, B., & Van Gool, L. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364910365417 · Cited by 191
Blocking and array contraction across arbitrarily nested loops using affine partitioning
Lim, A. W., Liao, S.-W., & Lam, M. S. (2001) · Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming · doi:10.1145/379539.379586 · Cited by 142
Pippia, T., Sijs, J., & De Schutter, B. (2020) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2019.2945023 · Cited by 58
The Complexity of Relating Quantum Channels to Master Equations
Cubitt, T. S., Eisert, J., & Wolf, M. M. (2012) · Communications in Mathematical Physics · doi:10.1007/s00220-011-1402-y · Cited by 44
Metadata
- Authors
- Letchford, A. N., & Schrijver, A.
- Venue
- The Journal of the Operational Research Society
- Publisher
- JSTOR
- Published
- 2000-07
- Volume
- 51
- Issue
- 7
- Pages
- 892
- ISSN
- 0160-5682 (ISSN-L)
- OpenAlex
- W1963547452
- Cited by
- 5,515
- References
- 0
- FWCI
- 259.66
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.