首页 | 本学科首页   官方微博 | 高级检索  
     检索      


The Wide Partition Conjecture and the Atom Problem in Discrete Tomography
Institution:1. CNRS and LIP6, Université Pierre et Marie Curie, Paris, France;2. Departamento Ingeniería Industrial, Universidad de Chile;1. Universidad Nacional de Rosario, Argentina;2. CONICET and Universidad Nacional de Rosario, Argentina;3. University of Waterloo, Canada;1. Institute of Math. Sciences, IV Cross Road, Taramani, Chennai 600 113, India;2. School of Comp. Science, Simon Fraser University, Burnaby, Canada V5A 1S6;3. DIMAP and Math. Institute, University of Warwick, Coventry CV4 7AL, UK
Abstract:The Wide Partition Conjecture (WPC) was introduced by Chow and B. Taylor as an attempt to prove inductively Rotaʼs Basis Conjecture, and in the simplest case tries to characterize partitions whose Young diagram admits a “Latin” filling. Chow et al. T. Chow, C. K. Fan, M. Goemans, and J. Vondrak. Wide partitions, latin tableaux, and rotaʼs basis conjecture. Adv. in Appl. Math., 31(2):334–358, 2003] showed how the WPC is related to problems such as edge-list coloring and multi commodity flow. As far as we know, the conjecture remains widely open.We show that the WPC can be formulated using the k-atom problem in Discrete Tomography C. Dürr, F. Guíñez, and M. Matamala. Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography. SIAM J Discrete Math, 26(1):330, 2012.]. In this approach, the WPC states that the sequences arising from partitions admit disjoint realizations if and only if any combination of them can be realizable independently. This realizability condition is not sufficient in general. A stronger condition, the saturation condition, was used in F. Guíñez, M. Matamala, and S. Thomassé. Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem. Discrete Appl.Math., 159(1):23–30, 2011] to solve instances were the realizability condition fails. We prove that in our case, the saturation condition is satisfied providing the realizability condition does. Moreover, we show that the saturation condition can be obtained from the Langrangean dual of a natural LP formulation of the k-atom problem.
Keywords:Wide partition conjecture  Discrete Tomography
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号