Abstract
Consider a \(\{0,1\}\) assignment matrix where each column contains exactly one coefficient equal to 1 and let h be the index of the lowest row that is not identically equal to the zero row. We give a full description of the convex hull of all feasible assignments appended with the extra parameter h. This polytope and some of its variants naturally appear in the context of several combinatorial optimization problems including frequency assignment, job scheduling, graph orientation, maximum clique, etc. We also show that the underlying separation problems are solvable in polynomial time and thus optimization over those polytopes can be done in polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ben-Ameur, W., Glorieux, A., Neto, J.: On the most imbalanced orientation of a graph. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 16–29. Springer, Heidelberg (2015)
Cook, W., Cunningham, W., Pulleyblank, W., Schrijver, A.: Combinatorial optimization (1997). ISBN: 978-0-471-55894-1
Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1990)
Hochbaum, D., Shmoys, D.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539–551 (1988)
Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J. ACM 23(2), 317–327 (1976)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. Plenum Press, New York (1972)
Koster, A.: Frequency assignment - models and algorihtms. Ph.D. thesis, University of Maastricht, The Netherlands (1999)
Mann, Z., Szajkó, A.: Complexity of different ILP models of the frequency assignment problem. In: Mann, Z.Á. (ed.) Linear Programming - New frontiers in Theory and Applications, pp. 305–326. Nova Science Publishers, New York (2012)
Martins, P.: Extended and discretized formulations for the maximum clique problem. Comput. Oper. Res. 37(7), 1348–1358 (2011)
Vazirani, V.: Minimum makespan scheduling. In: Vazirani, V.V. (ed.) Approximations Algorithms, vol. 10, pp. 79–83. Springer, Heidelberg (2003)
Wolsey, L.: Integer Programming (1998). ISBN: 978-0-471-28366-9
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Ben-Ameur, W., Glorieux, A., Neto, J. (2016). A Full Description of Polytopes Related to the Index of the Lowest Nonzero Row of an Assignment Matrix. In: Cerulli, R., Fujishige, S., Mahjoub, A. (eds) Combinatorial Optimization. ISCO 2016. Lecture Notes in Computer Science(), vol 9849. Springer, Cham. https://doi.org/10.1007/978-3-319-45587-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-45587-7_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45586-0
Online ISBN: 978-3-319-45587-7
eBook Packages: Computer ScienceComputer Science (R0)