text:
# The Impact of the Chemical Stratification of White Dwarfs on the Classification of Classical Novae

## 1 Introduction

Classical nova outbursts are powered by thermonuclear runaways (hereafter, TNRs) that take place in the accreted envelopes of white dwarfs in close binary systems (Starrfield et al. 1972). Observationally, classical novae are classified into different categories, based on detailed analysis of the decline of the light curve (fast versus slow novae), and also on the chemical pattern spectroscopically inferred from the ejecta (CO versus ONe novae). Atomic abundance determinations from the ejecta of several well-observed novae have provided a very useful tool to constrain theoretical models of the explosion. Significant progress was achieved after the discovery of the large metallicities that characterize the nova ejecta, with values ranging from 0.043 for Nova RR Pic 1925 (Williams & Gallagher 1979) to 0.86 for Nova V1350 Aql 1982 (Andrëa et al. 1994; Snijders et al. 1987). In order to account for this effect, the modeling of the explosion required some mixing between the solar-like material (transferred from the large, Main Sequence companion on top of the white dwarf by Roche lobe overflow) and the outermost layers of the underlying white dwarf. The reason is twofold: on one hand, at the typical temperatures expected during the course of the TNR, the amount of leakage from the CNO cycle is very limited (José & Hernanz 1998), and hence, the observed abundances of elements ranging from Ne to Ca (significantly overproduced with respect to solar proportions in some novae) cannot be explained in a natural way in terms of nuclear burning processes. Secondly, models computed with an envelope of solar metallicity are unable to reproduce the gross observational features of classical novae. Several mechanisms have been proposed to account for this mixing, including diffusion induced convection (Prialnik & Kovetz 1984; Kovetz & Prialnik 1985; Iben, Fujimoto & MacDonald 1991, 1992; Fujimoto & Iben 1992), shear mixing (MacDonald 1983, Livio & Truran 1987), convective overshoot induced flame propagation (Woosley 1986) or convection induced shear mixing (Kutter & Sparks 1989). Several multidimensional effects have also been tested with the recent development of two- and/or three-dimensional codes (Glasner, Livne & Truran 1997; Kercek, Hillebrandt & Truran 1998, 1999; Glasner & Livne 2002), including mixing by non-gravity wave breaking on white dwarf surfaces (Rosner et al. 2001; Alexakis et al. 2003).

Despite of the efforts carried out so far in the search for this mixing mechanism, there is not yet a satisfactory and self-consistent explanation capable to account for the wide spread in metallicities inferred from nova ejecta. So far, the usual assumption is to arbitrarily parametrize the mixing at the onset of the accretion phase, guided by observational grounds (Politano et al. 1995). Either through this crude approach or by means of a real physical mechanism, yet unknown, one of the important ingredients in the mixing involves the nature of the underlying white dwarf star. Moreover, the pioneeing discovery of Ne in the ejecta of Nova V1500 Cygni 1975 (Ferland & Shields 1978; Lance et al. 1988), Nova V1370 Aql 1982 (Snijders et al. 1984, 1987; Andrëa et al. 1994), Nova V693 CrA 1981 (Williams et al. 1985; Andrëa et al. 1994; Vanlandingham et al. 1997) and Nova QU Vul 1984 (Andrillat & Houziaux 1985; Gehrz, Grasdalen & Hackwell 1985; Andrëa et al. 1994; Saizar et al. 1992; Austin et al. 1996) was of significant importance, since it clearly pointed out the existence of two classes of nova outbursts: those showing large amounts of Ne in the spectra, overabundant with respect to the solar value, and those mainly enriched in C and O (see Table 2 in Gehrz et al. (1998) for a large sample of mass fractions inferred from optical and ultraviolet spectroscopy). This dicotomy essentially results from stellar evolution: whereas CO white dwarfs are the remnants of the evolution of intermediate-mass stars (M $`810\mathrm{M}_{}`$) that undergo hydrogen and helium burning (leaving a compact object that is C- and O-rich), slightly more massive stars (up to $`11\mathrm{M}_{}`$) undergo another evolutionary phase, carbon burning, leaving an ONe-rich object instead. The reader is referred to Starrfield, Sparks & Truran (1986) for the first hydrodynamic models of novae involving ONe(Mg) white dwarfs.

In the last decades, many efforts have been devoted to outline the nucleosynthesis accompanying nova outbursts (see José 2002, and references therein). In fact, a direct comparison between models and observations tells us that the overall nucleosynthetic picture is reasonably well understood: not only the endpoint for nova nucleosynthesis (around Ca) but also the atomic abundances inferred from the ejecta (Gehrz et al. 1998) are well reproduced (José & Hernanz 1998), with no major flaws, despite of the long-standing problems associated with the modeling of the explosion.

In this Letter, we analyze the impact of the specific choice of the chemical pattern of the outermost layers of massive (ONe) white dwarf cores in the composition of the ejecta, a subject that has deserved no particular attention in the literature despite of its importance.

## 2 Results

Contrary to the usual assumption, that adopts as the composition of the outermost layers of the white dwarf that of the ’bare’ ONe core, we take here into account the chemical stratification of the interior. More specifically, we estimate the role played by the presence of a thick CO-buffer that remains on top of the ONe-rich core, according to the recent stellar evolutionary models computed by García–Berro, Ritossa, & Iben (1997), for stars in the mass range $`8`$ M/$`\mathrm{M}_{}`$ $`<11`$. Such stars form an ONe core, after burning C in a partially degenerate core. The chemical structure of the abovementioned CO-buffer is shown in Fig. 1 (right panel): it is characterized by a very flat profile with similar amounts of 12C and 16O, plus traces of 25Mg and 22Ne. It is worth noticing that although all models within this mass range end up with a CO-buffer on top of the ONe core, its size depends strongly on the specific value of the mass of the progenitor at the Main Sequence (see, for instance, Gil–Pons & García–Berro 2001, 2002; Gil–Pons et al. 2003). Nevertheless, for the scope of this paper, it is enough to say that the C/O fraction in such CO-buffers is rather independent of the mass of the progenitor. Hence, the structure displayed in Fig. 1, corresponding to the evolution of a single 9 $`\mathrm{M}_{}`$ star (García–Berro et al. 1997) can be regarded as representative. Another common issue for all models in this mass range is the existence of a transition zone that connects the CO-buffer and the ONe-rich core of the white dwarf, through a region (Fig. 1, middle panel) characterized by steep chemical profiles (see, for instance, 12C, 20Ne, or 24Mg). The pattern shown in Fig. 1 (middle panel), corresponds indeed to a typical abundance profile of the trasition zone, for stars in this mass range.

It is not clear whether this CO-rich buffer (and/or the transition zone) is lost in the late stages of the evolution of the star or rather, if accretion settles on top of this layer, a possibility that has been ignored in previous works. In this Letter, we analyse this issue by performing a series of hydrodynamic calculations of classical nova outbursts, and discuss its impact on the resulting explosion as well as on the accompanying nucleosynthesis. Calculations have been performed with the Shiva code, a spherically-symmetric, implicit, hydrodynamic code, in Lagrangian formulation (see José & Hernanz 1998, for details) that follows the course of the explosion from the onset of accretion up to the explosion and ejection stages. The calculations presented here are similar to those published in previous papers except for the chemical composition adopted for the envelope. Here, we assume that the solar-like accreted material is mixed either with material from the CO-buffer (hereafter, Model C), or with material from the transition zone (Model B). It is worth noticing that the second case implicitly assumes that the former CO-buffer has been lost during previous evolution. Both models assume that the TNR takes place on top of a $`1.25\mathrm{M}_{}`$ white dwarf that is accreting material from a Main Sequence companion at a rate of $`2\times 10^{10}\mathrm{M}_{}\mathrm{yr}^1`$. As in previous papers (see discussion in José & Hernanz 1998), and due to the lack of a fully self-consistent mechanism of mixing, capable to account for metallicity enrichments as high as 0.86 by mass, we adopt the usual approach of an arbitrary mixing ratio between the solar-like accreted material and the outermost layers of the white dwarf at the onset of accretion (see Politano et al. 1995). For the calculations reported in this paper a 50% mixing ratio (representative of the average metallicity inferred from ’neon’ novae) has been adopted. The impact of this crude approximation on the evolution of the outburst is extensively discussed in Starrfield et al. (1998). Results from the two evolutionary sequences are summarized in Table 1. For the purpose of comparison, we included also results from a third hydrodynamic computation of a similar model (i.e., Model A), for which mixing with material from the ’bare’ ONe core is assumed. This material is characterized by large amounts of 16O and 20Ne, however the specific prescription depends crytically on details of the previous stellar evolutionary phases. For instance, all the hydrodynamic models of nova outbursts computed by Starrfield et al. (1998), and references therein, adopt an ONeMg composition based on C-burning nucleosynthesis by Arnett & Truran (1969), which is characterized by large amounts of not only 16O and 20Ne, but also 24Mg, with a ratio X(16O):X(20Ne):X(24Mg) = 1.5:2.5:1. In this Letter, as well as in previous work, we use the most recent prescription for ONe white dwarf composition, for which X(16O):X(20Ne):X(24Mg) = 10:6:1 (Ritossa, García–Berro, & Iben 1997). It is worth noticing that both prescriptions have quite remarkable differences in the amount of 24Mg and hence, a significantly different chemical pattern is expected for the ejecta (in particular, the contribution of novae to the Galactic 26Al content, a hot topic in gamma-ray astronomy).

A critical issue in the evolution of the models listed in Table 1 is the initial amount of 12C in the envelope: since the main nuclear reaction that triggers the TNR is 12C(p,$`\gamma `$), models with large initial 12C abundances (i.e., Model C) will release large amounts of energy by CNO-reactions, and hence, will easily achieve the critical conditions to power a TNR. As a result, the initial 12C content determines not only the amount of mass accreted prior to the TNR (and hence, the pressure at the base of the accreted envelope), but also the strength of the explosion (i.e., $`\mathrm{T}_{\mathrm{peak}}`$), the amount of mass ejection by the outburst ($`\mathrm{\Delta }\mathrm{M}_{\mathrm{ejec}}`$), and its mean kinetic energy ($`\mathrm{K}_{\mathrm{ejec}}`$), as well as the characteristic timescales of the explosion (accretion phase, rise time to $`\mathrm{T}_{\mathrm{peak}}`$, …). Such differences are reported in Table 1. Because of the lower amount of energy released by 12C(p,$`\gamma `$) reactions as the initial amount of 12C decreases, model A accumulates more mass than models B and C: the difference between the two extreme cases, model A —that assumes mixing with a ’bare’ ONe core— and model C —that involves material from the thick CO-buffer— is nearly a factor of two in the accreted envelope mass. Furthermore, both $`\mathrm{t}_{\mathrm{rise}}`$ (i.e., time required for the innermost envelope shell to evolve from a temperature of $`3\times 10^7`$ K up to $`10^8`$ K) and $`\mathrm{t}_{\mathrm{max}}`$ (i.e, time spent by the innermost shell between $`10^8`$ K and $`\mathrm{T}_{\mathrm{peak}}`$) clearly increase as we decrease the initial amount of 12C in the envelope. For instance, model A takes $`\mathrm{t}_{\mathrm{rise}}=1.21\times 10^7`$ sec to reach a temperature of $`10^8`$ K at the base of the envelope (also, $`\mathrm{t}_{\mathrm{max}}=313`$ sec), whereas model C, reaches $`10^8`$ K much faster, $`\mathrm{t}_{\mathrm{rise}}=2.5\times 10^5`$ sec (and $`\mathrm{t}_{\mathrm{max}}=45`$ sec). Model B can be regarded as an intermediate model between both.

A direct consequence of the abovementioned differences is that the outburst, whose strength is directly determined by the pressure at the base of the envelope (or conversely, by the amount of mass accreted), will have a clear imprint in the ejected envelope shells. A first one, involves the amount of material ejected by the explosion and its expansion velocity: as an example, model A ejects $`1.8\times 10^5\mathrm{M}_{}`$, with a mean kinetic energy of $`\mathrm{K}_{\mathrm{ejec}}=1.5\times 10^{45}`$ ergs s-1, whereas model C ejects $`10^5\mathrm{M}_{}`$ (almost a factor of 2 lower), with a mean kinetic energy of $`\mathrm{K}_{\mathrm{ejec}}=10^{45}`$ ergs s-1. A second imprint is found in the accompanying nucleosynthesis (see Table 1), which is very sensitive to the characteristic timescales of the explosion as well as to the maximum temperatures reached during the TNR (model A reaches $`\mathrm{T}_{\mathrm{peak}}=2.5\times 10^8\mathrm{K}`$, whereas the less violent outburst in model C reaches only $`\mathrm{T}_{\mathrm{peak}}=2.2\times 10^8\mathrm{K}`$). This is, for instance, the case of 7Li, strongly enhanced in the ejecta of model C because of the rapid rise time to temperatures of the order of $`10^8`$ K, where efficient 8B($`\gamma `$,p)7Be photodisintegration reactions prevent significant destruction of 7Be, which is transformed into 7Li by electron captures in the cold, ejected envelope shells (Hernanz et al. 1996). The larger initial 12C abundance of this model is also responsible for the moderate increase in the final 12,13C and 14,15N yields, which translates into a slightly larger (i.e., a factor of 2) 14N/15N isotopic ratio for model C. A clear imprint of the decrease in the peak temperatures as the initial amount of 12C increases can be seen in the increasing final 16O yield. On the contrary, no significant effect is found in the final 18F content and therefore, the expected prompt gamma-ray output at 511 keV and below seems to be unaffected by the presence of a thick CO-buffer. Furthermore, model C shows a dramatic decline in the final 20Ne and 22Na yields, a direct consequence of the low initial 20Ne content for this model. Hence, model C would provide observational features (in particular the lack of significant overabundances of Ne in the spectra) typical of a CO novae rather than an ONe one. However, it is worth mentioning that 26Al is not very much affected by the presence of the CO-buffer because of the large amounts of the ’seed’ 25Mg both in the transition zone as well as in the buffer itself (see Fig. 1). Therefore, we can end up with a quite ’weird’ nova explosion, ressembling a CO nova, but with simultaneous ejection of 7Li and 26Al, among additional peculiar features mentioned above.

## 3 Discussion and conclusions

In this Letter, we have shown that classical nova outbursts on top of ONe white dwarfs with thick CO-buffers may lead to the ejection of significant amounts of both 7Li and 26Al, usually predicted to be synthesized in different nova types (CO and ONe novae, respectively). In turn, due to the lack of significant amounts of neon in the ejecta, such explosions may be (wrongly?) classified as CO novae.

It is very difficult (and out of the scope of this paper) to estimate the number of ’weird’ nova explosions as compared with the number of normal novae, in particular because the thickness of both the CO-buffer and the C-rich trasition zone depend critically on the mass of the progenitor star (see Gil-Pons et al. 2003, for details). However, we have estimated the number of outbursts required to completely get rid of the CO-buffer and the transition zone, assuming that in each explosion, 50% of the ejecta corresponds to material eroded from the interior (either from the buffer or from the transition zone). For this purpose, we adopt the values given in García–Berro et al. (1997), corresponding to the evolution of a single 9 $`\mathrm{M}_{}`$ star, whose chemical profiles have been adopted in this paper: a thickness of 0.0264 $`\mathrm{M}_{}`$ for the CO-buffer and 0.0236 $`\mathrm{M}_{}`$ for the transition zone. Around 7300 outbursts will be required before a nova with standard composition will show up. It has to be emphasized, however, that the discovery of ’neon’ novae is a clear evidence that, at least in some cases, such CO-buffers are lost before the onset of accretion. Otherwise, it would not be possible to find overabundances of Ne in the ejecta of such systems and therefore, the ’neon’ (or ONe) nova class would not exist at all. Therefore, it remains to be analyzed in detail whether such CO-buffers are systematically lost during the previous evolution or they may remain and give rise to some ’weird’ nova explosions.

We thank an anonymous referee for valuable comments to the manuscript. This work has been partially supported by the MCYT grants AYA2001-2360 and AYA2002-0494C03-01, by the CIRIT and by the E.U. FEDER funds.


format: text

text:
# Sagittarius Tidal Debris 90 kpc from the Galactic Center

## 1 Introduction

The discovery of the Sagittarius dwarf galaxy (Ibata, Gilmore, and Irwin, 1994), which is in the process of being tidally disrupted by the gravitational field of the Milky Way galaxy, has sparked a decade of research on the nature, extent, and formation history of its tidal tails. Underlying the quest for the details of this merger event in our own galaxy is the hope that it will lead to a better understanding of halo formation processes in general and the formation of the Milky Way galaxy in particular. Additionally, the tidal streams can be used as a probe of the Galactic potential, and the clumpiness of the halo dark matter component.

In this letter, we present evidence that a piece of the Sagittarius dwarf tidal stream extends to a distance of up to 90 kpc from the Galactic Center. This doubles the known extent of the trailing tidal tail. These stars will help constrain models of the Galactic potential and the disruption of the Sgr dwarf.

## 2 Observations and Data

The SDSS scans the sky in 2.5 degree wide stripes that follow great circles on the sky. Details of the survey geometry may be found in Stoughton et al. (2001) and Abazajian et al. (2003). Other SDSS technical details can be found in: Fukugita et al. (1996), Gunn et al. (1998), Hogg et al. (2001), Pier et al. (2002), Smith et al. (2002), and York et al. (2000).

SDSS imaging data available 2003 March was searched for clumps of faint blue stars, following the techniques described in Yanny, Newberg et al. (2000), hereafter Paper I, for selecting stars of type A. These stars are bluer than the turnoff of the Galactic thick disk, thereby minimizing contamination from this component. A-type stars (including many Blue Horizontal Branch - BHB - objects), are selected with $`(ug)_0>0.4`$ (to avoid contamination from extragalactic quasars) and $`0.3<(gr)_0<0`$. This ‘standard candle’ population was used to explore the stellar halo structure out to distances of $`100`$ kpc from the Sun.

Table 1 lists the SDSS stripes examined for which detections near the plane of the Sgr dwarf orbit (Ibata et al., 2001b) were noted. Listed are the stripe number, stripe inclination, Galactic latitude and longitude of the center of intersection of the Sagittarius stream with the observed SDSS stripe, mean $`g`$ magnitude of the BHB stars in the stream, a derived distance to the stream stars, and rough number counts, $`N`$, of type A stars in each stripe which crosses the stream, along with the angle between the A star distribution and the end of the stripe. Note that the stripes overlap and thus the numbers may not be summed without accounting for the overlap. About 20% of the BHBs are listed twice in the Table, due to the overlap of adjacent stripes. The number counts of A stars were determined by counting the number of A stars within 0.2 magnitudes of the tabulated $`g`$ magnitude, and within $`20^{}`$ of the tabulated position. A reasonable background A star count was estimated from a histogram of apparent magnitudes in each direction and has been subtracted. We note qualitatively that the spatial density of BHB stars remains approximately as high at 90 kpc from the Galactic Center (stripes 27 through 37) as it does for trailing tail stripes 82 and 86, only 30 kpc from the G.C.

## 3 Detection of a new density enhancement in the Galactic halo

Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center shows a polar wedge (magnitude, angle) diagram for type A/BHB objects in the SDSS stripe 29. The most striking new feature is the overdensity of A-type stars at $`g_0=20.3`$ (where the subscript indicates the magnitude has been dereddened by the standard Schlegel, Finkbeiner, & Davis (1998) maps) and $`(l,b)=(195^{},29^{})`$. There is another apparent overdensity of A-type stars with $`g_017.5`$ (apparent also in Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center). The source of these stars is unclear. They could be blue stragglers in the new structure discovered in the plane of the Milky Way (Yanny, Newberg et al., 2003). Alternatively, they could be associated with a Galactic disk structure or a closer piece of debris from the Sgr dwarf galaxy.

Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center shows the $`g_0`$ magnitude of all A-type stars in stripes 27-37 with $`100^{}<\alpha <170^{}`$ and within 15 kpc of the Sgr dwarf tidal plane, as defined in Majewski et al. (2003) (see §4), as a function of $`\mathrm{\Lambda }_{}`$. $`\mathrm{\Lambda }_{}`$ was defined by Majewski et al. (2003) to be the angular distance from the Sgr dwarf, in the plane of the Sgr dwarf orbit. This figure can be compared with Figure 8 of Majewski et al. (2003). From Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center, this tidal fragment (at $`g_020.3`$) extends at least $`20^{}`$ on the sky ($`173^{}<\mathrm{\Lambda }_{}<148^{}`$). If one adjusts for the fact that the stripe in Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center is not perpendicular to the Sgr orbit (which makes the stream appear wider), we find that the stream is at least 10 degrees across. When this overdensity was discovered, it was not in a targeted search for stars in the Sgr stream, but it was the most significant new substructure discovered in a routine search through the entire SDSS data set collected to date.

Since this identified overdensity is narrowly concentrated in apparent magnitude, we tentatively identify this as a population of blue horizontal branch (BHB) stars associated with a tidal stream in the outer halo. Using an absolute magnitude of $`M_g0.7`$ (Paper I), the tidal stream is 83 kpc from the Sun and at least 15 kpc in width. With a position $`(l,b)=(190^{},30^{})`$, the overdensity is 90 kpc from the Galactic center.

Note the ‘finger of God’ at $`(\mathrm{\Lambda }_{},g_0)=(170^{},20.3)`$. These are the horizontal branch stars from the globular cluster NGC 2419 ($`[l,b]=[180^{},25^{}]`$). The magnitude of the horizontal branch is less than a tenth of a magnitude different from those of our newly identified distant tidal stream. NGC 2419 is 13 kpc above the Sgr dwarf orbital plane. This cluster could have once belonged to the Sgr dwarf galaxy or some parent progenitor to today’s Sgr dwarf. The fact that this cluster is relatively close the the plane of the Sgr dwarf tidal debris has also been noticed by Zhao (1998).

The globular cluster NGC 2419 has a heliocentric radial velocity of -20 km/s (Peterson, Olszewski, & Aaronson, 1986). This translates to a radial velocity of -14 km/s in the rest frame of the Galactic center, but as seen from the Sun. Since the Sun and the Galactic center are only about $`2^{}`$ apart as seen from NGC 2419, the radial velocity as seen from the Sun should be close to the radial velocity as measured from the Galactic center. If the globular cluster is in a portion of the stream that is near apogalacticon, as suggested by our results, the galactocentric radial velocity should be near zero. With a velocity dispersion of 20 km/s (Yanny, Newberg et al., 2003), the observed radial velocity is consistent with its association with the Sgr dwarf tidal stream near its apogalacticon.

We have confirmed the identification of the A-colored stars as horizontal branch stars by identifying an excess of RR Lyrae candidates with the correct apparent magnitudes in this position. We selected stars in the overlaps of stripes 27 through 37 which were observed at multiple epochs. Ordinarily this SDSS stripe-to-stripe overlap is about 20% of the area of the sky. However, since these observations are near the beginning and ends of SDSS survey stripes (near the survey poles) the stripes converge, significantly increasing the overlap. The matching routine first selected objects with $`16<g_0<22`$ in the color range $`0.2<(gr)_0<0.3`$, and chose stellar objects at the same spatial position (within $`1^{\prime \prime }`$) from the list which were observed more than once. We compared the matches in the area $`110^{}<\alpha <130^{}`$, $`20^{}<\delta <50^{}`$ with a wider ‘control’ area with a similar number of matches over the whole of the stripes covering $`165^{}<\alpha <260^{},20^{}<\delta <65^{}`$.

There are about 50 excess variable objects with magnitude differences of at least 0.4 magnitudes between the two observations in the magnitude range $`20<g<21`$ (57 in the first region vs. 5 in the control region). This sample of RR Lyrae candidates provides strong confirmation that the blue A-type stars seen in Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center and Sagittarius Tidal Debris 90 kpc from the Galactic Center near the plane of the Sgr dwarf orbit, some 81-85 kpc from the Sun, are indeed BHB stars and not intrinsically fainter (and thus more nearby) blue straggler objects of the same color (Paper I).

## 4 The trailing tail of the Sagittarius tidal stream

We compare our detection with the positions of the Sgr tidal tails of 2MASS M-stars as presented by Majewski et al. (2003). In order to put our data on their Figure 11, showing the tidal tails, we adopt their distance from the Sun to the center of the Galaxy of 8.5 kpc. Our Galacitic X-axis is along the line from the Sun to the center of the Galaxy, but incontrast to Majewski et al. (2003) it is measured from the Galactic center towards $`l=0^{}`$, so that the Sun is at $`X=8.5`$ kpc. $`Y`$ ($`l=90^{}`$) and $`Z`$ ($`b=90^{}`$) are unchanged. Using our definitions, the Sgr plane is:

$`0.064X+0.970Y+0.233Z+0.232=0.`$

The same paper defines another coordinate system, $`(X_{Sgr,GC},Y_{Sgr,GC},Z_{Sgr,GC})`$, where $`Z_{Sgr,GC}`$ is perpendicular to the plane of the orbit, and $`Y_{Sgr,GC}=0`$ in the Galactic plane. Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center shows the 2MASS M stars from Figure 11 of Majewski et al. (2003), along with the positions (large open circles) of the stream we detect in SDSS A-stars in stripes 29-37. Also shown are other detections of the tidal tails of Sgr in SDSS A-stars, by methods described in Newberg, Yanny et al. (2002). Open circles denote the trailing tail, and filled circles mark the leading tail. The error bars are three sigma error bars, but do not include systematic error which would arise if the absolute magnitudes of our selected A stars were not $`M_{g_0}=0.7`$. We measure the central apparent magnitude of each overdensity to within 0.05 magnitudes in $`g_0`$, and the position along the stripe of data to within one degree. We added in quadrature the errors in distance from the center of the Galaxy that would arise from a difference of 0.15 magnitudes in apparent magnitude and from a difference of $`3^{}`$ in stream center. The data points for the distant portion of the stream were determined from the entire dataset of A-type stars converted to $`\mathrm{\Lambda }_0,g_0`$ coordinates; their positions are not tied to individual SDSS stripes, but spaced according to the density of stars in Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center, excluding NGC 2419.

There appears to be a systematic scale difference between the distance to the Sgr stream from 2MASS M star statistics and from A star statistics. The A star distance scale used in Paper I was based on the somewhat arbitrary assumption that the blue horizontal branch (BHB) stars in the sample had absolute magnitudes of $`M_{g_0}=0.7`$. Note, however, that the distances given in Paper I to pieces of the Sgr tidal stream from BHB stars are not far from the distances quoted in Ivezić et al. (2000) and Vivas et al. (2001) to similar sections of the stream using RR Lyrae stars. The nominal distance to NGC 2419 is 81 kpc (Harris, et al., 1997) from the Sun, in excellent agreement with our measured distance to the tidal stream. The M-star distance scale is calibrated assuming a distance of 24 kpc from the Sun to the Sgr dwarf, 12.5% smaller than the distance to M54 measured by Layden & Sarajedini (2000) using RR Lyrae stars. If the larger distance scales for A-stars and RR Lyraes are correct, then either the M-star population changes as a function of position along the stream (as suggested by Martinez-Delgado 2003), or the Sgr dwarf is somewhat more distant than typically assumed. Alternatively, the absolute magnitudes of the BHB and RR Lyrae stars could be $`0.26`$ magnitudes fainter than we have previously assumed.

The newly discovered overdensity of A-type stars may coincide with an overdensity of M giants on the left edge of Figure 9 of Majewski et al. (2003). These stars appear to extend the trailing tail of the Sgr dwarf back up through the Galactic plane into the northern Galactic hemisphere. Our result suggests that these M-stars may in fact be a part of a longer trailing tail of the Sgr dwarf, which extends to 90 kpc from the Galactic center.

Figure Sagittarius Tidal Debris 90 kpc from the Galactic Center shows the positions of the same pieces of tidal debris, but shown as a cross section through the plane of the Sgr dwarf tidal stream. The exact position of the center of the tidal stream is uncertain for the distant portion of the tidal stream, since we do not unambiguously detect the entire cross section in any stripe, and in many stripes we detect only a portion of the cross section. The $`3\sigma `$ asymmetrical error bars reflect this fact. If we adopted a larger absolute magnitude for the A-type stars, then position of the points on the X-axis would shift somewhat but the positions and errors on the Z-axis would hardly change. Notice that the leading arm of Sgr shifts towards larger (positive) $`Z_{Sag}`$ as we go back towards the Sgr dwarf. The trailing arm (closer than 50 kpc) is less well sampled, but possibly shifts towards smaller (negative) $`Z_{Sag}`$ as we go towards the Sgr dwarf. This may indicate that the leading arm originates at positive $`Z_{Sag}`$ and the trailing arm at negative $`Z_{Sag}`$. The slight deviations from the plane might alternatively result from a non-spherical Galactic potential. These deviations cannot be reduced by redefining the Sgr orbital plane.

## 5 Conclusions

We have detected an overdensity of A-type stars with an estimated distance of 90 kpc from the Galactic center. The globular cluster NGC 2419 appears to be within this overdensity, which is in nearly the same plane as the previously discovered tidal tails of the Sgr dwarf galaxy. The radial velocity of NGC 2419 is consistent with its association with the tidal stream, near the apogalacticon of its orbit. The position of the overdensity is consistent with identification as a distant piece of the trailing tail of the Sgr dwarf galaxy, and coincident with the positions of Sgr dwarf M giants discovered in 2MASS. The inferred distances to the M giants are 13% smaller than those from BHB and RR Lyrae stars in the Sgr stream. This may indication a systematic error in one or both of the distance scales.

HJN acknowledges funding from Research Corporation and the National Science Foundation (AST-0307571). We are grateful to S. Majewski for permission to reproduce a figure of 2MASS M giant stars in the stream. We thank the referee, Helio J. Rocha-Pinto, for his kind suggestions. Funding for the creation and distribution of the SDSS Archive has been provided by the Alfred P. Sloan Foundation, the Participating Institutions, the National Aeronautics and Space Administration, the National Science Foundation, the U.S. Department of Energy, the Japanese Monbukagakusho, and the Max Planck Society. The SDSS Web site is http://www.sdss.org/. The SDSS is managed by the Astrophysical Research Consortium (ARC) for the Participating Institutions. The Participating Institutions are The University of Chicago, Fermilab, the Institute for Advanced Study, the Japan Participation Group, The Johns Hopkins University, Los Alamos National Laboratory, the Max-Planck-Institute for Astronomy (MPIA), the Max-Planck-Institute for Astrophysics (MPA), New Mexico State University, University of Pittsburgh, Princeton University, the United States Naval Observatory, and the University of Washington.


text:
# Convex Combinatorial Optimization

## 1 Introduction

The general linear combinatorial optimization problem is the following.

Linear Combinatorial optimization. Given a family $`2^N`$ of subsets of $`N:=\{1,\mathrm{},n\}`$ and a rational weighting $`w:N`$, find $`F`$ of maximum weight $`w(F):=_{jF}w(j)`$.

There is a massive body of knowledge on the computational complexity of this problem for various classes of families presented in various ways (in terms of $`n`$ and sometimes additional parameters), and efficient algorithms in numerous cases, cf. . For instance, if $``$ is the family of stable sets in a given graph with vertex set $`N`$ then the problem is NP-hard whereas if $``$ is the family of matchings in a given graph with edge set $`N`$ then the problem is polynomial time solvable.

In this article we consider the following generalization of linear combinatorial optimization.

Convex combinatorial optimization. Given $`2^N`$ with $`N=\{1,\mathrm{},n\}`$, a vectorial weighting $`w:N^d`$, and a convex functional $`c:^d`$, find $`F`$ of maximum value $`c(w(F))`$.

The standard linear combinatorial optimization problem over a family $``$ is recovered as the special case with $`d=1`$, $`w:N`$ weighting by scalars, and $`c::xx`$ the identity.

Convex combinatorial optimization has a very broad expressive power and conveniently captures a variety of problems studied in the operations research and mathematical programming literature including quadratic assignment, inventory management, scheduling, reliability, bargaining games, clustering, and vector partitioning, see  and references therein. In Section 3 we discuss some of these applications in detail and demonstrate that, as a consequence of our framework, all admit a simple unified strongly polynomial time algorithm.

A particularly successful general methodology for linear combinatorial optimization is the geometric approach inaugurated by Edmonds  and culminated in Grötschel-Lovász-Schrijver , outlined as follows. With each family member $`F`$ is associated its indicator $`\mathrm{𝟏}_F:=_{jF}\mathrm{𝟏}_j`$ with $`\mathrm{𝟏}_j`$ the $`j`$th standard unit vector in $`^n`$, and with the family is associated the polytope

$$𝒫^{}:=\text{conv}\{\mathbf{\hspace{0.17em}1}_F:F\}^n.$$

Extending $`w`$ to $`^n`$ by $`w(x):=_{j=1}^nw(j)x_j`$, the problem reduces to maximizing the linear functional $`w`$ over $`𝒫^{}`$. This leads to the study of facets of $`𝒫^{}`$; when these can be suitably controlled, the problem is polynomial time solvable via the ellipsoid method  for linear programming.

In this article we show that the geometric approach can be usefully exploited so as to yield a widely applicable general methodology for convex combinatorial optimization as well. Our framework leads to the study of edge-directions of $`𝒫^{}`$; when these can be suitably controlled, the problem is efficiently solvable via zonotope (or hyperplane arrangement) methods as follows.

###### Theorem 1.1

For any fixed $`d`$, there is a strongly polynomial oracle time algorithm solving convex combinatorial optimization over any edge-guaranteed family presented by a membership oracle.

The precise definition of an edge-guaranteed family will be given in Section 2: all families underlying the various applications in Section 3 naturally possess this property. The assumption of fixed $`d`$ is also natural and necessary: already for $`d=1`$, the problem generalizes linear combinatorial optimization which is frequently intractable; and when $`d`$ is variable, the problem captures NP-hard instances even for the simple power set family $`=2^N`$, see Example 3.1 below.

The main part of the proof of this theorem is a reduction of the convex combinatorial optimization problem over a family $``$ to the solution of polynomially many standard linear combinatorial optimization counterparts over the same family $``$. The reduction makes use of several results about zonotopes which are available in combinatorial and computational geometry, but have not been so far integrated and harnessed in a systematic way to discrete optimization.

The repeated solution of each of the standard linear combinatorial optimization counterparts can be done following either one of the following two approaches. The first is to use any efficient ad-hoc algorithm available in the literature for the specific family $``$ at hand: this typically leads to the best overall running time. This approach indeed applies to all of the applications discussed in Section 3, since each admits a very fast ad-hoc algorithm (ranging from simple greedy to sophisticated min-cost flow). The second approach, which is generic and works for any $``$, takes advantage of the fact that a test set (cf. ) is readily available for any edge-guaranteed family, and (see  and references therein), using scaling  and Diophantine approximation , allows the efficient solution of the necessary linear optimization counterparts.

The article is organized as follows. In Section 2 we prove Theorem 1.1 as well as some other results, and discuss some relevant issues, as follows. In §2.1 we discuss the necessary preliminaries on zonotopes and edge-directions. In §2.2 we prove Theorem 2.6 providing the reduction of convex combinatorial optimization to polynomially many standard linear combinatorial optimization counterparts. In §2.3 we discuss the generic approach for solving the counterparts and combine it with Theorem 2.6 to establish Theorem 1.1. In §2.4 we discuss the problem of finding short monotone paths on $`(0,1)`$-polytopes, provide Lemma 2.10 which is a certain $`(0,1)`$-analog of the Klee-Minty cube , and raise some questions. In §2.5 we consider classes of edge-guaranteed families and conclude Corollary 2.12 concerning such edge-well-behaved classes (defined therein). In §2.6 we discuss projection representation which sometimes helps control edge-directions. Section 3 is devoted to applications: in §3.1 we discuss quadratic assignment and matroids, whereas in §3.2 we make use of projection representation and discuss in detail the broadly applicable shape vector partitioning problem. The last Section 4 contains some final remarks and open problems.

We conclude this introduction with some comments. First, our results make use of and provide an efficient enumeration of the vertices of the polytope $`𝒫_w^{}:=\text{conv}\{w(F):F\}`$ which is a projection of $`𝒫^{}`$; as the maximum of a convex functional $`c`$ over $`𝒫_w^{}`$ is attained at a vertex and each vertex has the form $`w(F)`$ with $`F`$, this provides a strategy for addressing the convex combinatorial optimization problem. One of the difficulties we overcome is that the number of sets in $``$ is typically exponential in $`n`$ and hence it is generally impossible to construct $`𝒫_w^{}`$ directly efficiently. As a consequence of our efficient vertex enumeration of $`𝒫_w^{}`$, our results immediately extend to the larger class of problems where $`c`$ is any functional which is guaranteed to attain a maximum over $`𝒫_w^{}`$ at a vertex, e.g., when $`c`$ is (edge-)quasi-convex on $`𝒫_w^{}`$, see . In particular, our results extend to functions $`c`$ which are (asymmetric) Schur convex when the edge-directions of $`𝒫_w^{}`$ are differences of standard unit vectors in $`^d`$, again see . Also, the results can be generalized to some extent from $`(0,1)`$-problems to integer programming. Second, we note that in studying edge-directions, we make use of projections of polytopes; thus the Billera-Sturmfels theory of fiber polytopes , related to various aspects of polytope projection, may be helpful in the classification of edge-well-behaved classes of families. Also, some new questions that we raise about graphs of $`(0,1)`$-polytopes might be addressed through the Billera-Sarangarajan universal embedding of such polytopes as travelling salesman polytopes .

We hope this exposition will make our framework a widely accessible tool in the arsenal of discrete optimization, and will stimulate the study of edge-directions of polytopes $`𝒫^{}`$ for various combinatorially defined families. Since convex combinatorial optimization is often intractable, there is also much room for the study of approximation algorithms for this problem for various families $``$, and we hope this article will stimulate research on this yet unexplored ground.

## 2 Edge-Directions and the Algorithmic Solution

### 2.1 Edge-directions and zonotopes

We start by introducing the necessary terminology and collecting several facts that we shall make use of; for some we only provide a reference and for others we provide a short proof.

The zonotope generated by a set of vectors $`E=\{e^1,\mathrm{},e^m\}`$ in $`^d`$ is the Minkowsky sum

$$𝒵=\text{zone}(E):=\underset{i=1}{\overset{m}{}}[e^i,e^i]=\{\underset{i=1}{\overset{m}{}}\lambda _ie^i:1\lambda _i1\}=\text{conv}\{\underset{i=1}{\overset{m}{}}\lambda _ie^i:\lambda _i=\pm 1\}^d.$$

The following bound on the number of vertices of zonotopes has been rediscovered many times over the years; see e.g.  for early references and  for recent extensions and refinements.

###### Lemma 2.1

The number of vertices of any $`d`$-dimensional zonotope generated by $`m`$ vectors is at most $`2_{i=0}^{d1}\left(\genfrac{}{}{0pt}{}{m1}{i}\right)`$. Thus, for fixed $`d`$ it is $`O(m^{d1})`$ and hence polynomially bounded in $`m`$.

Each vector $`a^d`$ is also interpreted as the linear functional on $`^d`$ given via the standard inner product $`ax=_{i=1}^da_ix_i`$. The normal cone of a polytope $`𝒫`$ at its face $`F`$ is the (relatively open) cone $`𝒞_𝒫^F`$ of those linear functionals $`a`$ which are maximized over $`𝒫`$ precisely at points of $`F`$. The following computational analogue of Lemma 2.1 is provided by the algorithm in  (the latter reference provides a necessary correction of the former); some extensions are again in .

###### Lemma 2.2

Fix any $`d`$. Then all vertices of any $`d`$-dimensional zonotope $`𝒵`$ generated by $`m`$ given vectors can be listed, each vertex $`u`$ along with a linear functional $`a(u)𝒞_𝒵^u`$ uniquely maximized over $`𝒵`$ at $`u`$, in strongly polynomial time using $`O(m^{d1})`$ arithmetic operations.

Note that throughout we are mainly interested in strongly polynomial (oracle) time algorithms, that is, algorithms that perform a polynomial number of arithmetic operations (and calls to the relevant oracles if any) and are also polynomial time in the Turing computation model.

The collection of normal cones of a polytope $`𝒫`$ at all faces is called the normal fan of $`𝒫`$ (see ). A polytope $`𝒵`$ is a refinement of a polytope $`𝒫`$ if the closure of each normal cone of $`𝒫`$ is the union of closures of normal cones of $`𝒵`$. A standard result shows that $`𝒵`$ is a refinement of $`𝒫`$ if and only if the normal cone of every vertex of $`𝒵`$ is contained in the normal cone of some vertex of $`𝒫`$, and we will use this property interchangeably with the above definition of refinement. A direction of an edge $`[u,v]`$ of a polytope $`𝒫`$ is any nonzero scalar multiple of $`vu`$. We provide a simple proof of the following fact (cf. ) which is quite central to our considerations.

###### Lemma 2.3

Let $`𝒫`$ be a polytope and let $`E`$ be a finite set of vectors containing a direction of every edge of $`𝒫`$. Then the zonotope $`𝒵:=\text{zone}(E)`$ generated by $`E`$ is a refinement of $`𝒫`$.

Proof. Let $`E=\{z^1,\mathrm{},z^m\}`$. Consider any vertex $`u`$ of $`𝒵`$. Then $`u=_{i=1}^m\lambda _iz_i`$ for some $`\lambda _i=\pm 1`$ and hence its normal cone $`𝒞_𝒵^u`$ consists of those $`a`$ satisfying $`a\lambda _iz_i>0`$ for all $`i`$. Let $`v`$ be a vertex of $`𝒫`$ at which some such $`\widehat{a}`$ (belonging to $`𝒞_𝒵^u`$) is maximized over $`𝒫`$. Consider any edge $`[v,w]`$ of $`𝒫`$. Then $`vw=\alpha _iz_i`$ for some scalar $`\alpha _i0`$ and some $`z_i`$, and $`0\widehat{a}(vw)=\widehat{a}\alpha _iz_i`$, implying $`\alpha _i\lambda _i>0`$. It follows that every $`a`$ in the cone $`𝒞_𝒵^u`$ of the vertex $`u`$ of $`𝒵`$ satisfies $`a(vw)>0`$ for every edge of $`𝒫`$ containing $`v`$ and therefore $`a`$ is also in the cone $`𝒞_𝒫^v`$ of the vertex $`v`$ of $`𝒫`$, and hence $`𝒞_𝒵^u𝒞_𝒫^v`$. Since $`u`$ was arbitrary, it follows that the normal cone of every vertex of $`𝒵`$ is contained in the normal cone of some vertex of $`𝒫`$ and we are done by the aforementioned standard result.

Finally, we need the following statement about edge-directions of linear images of polytopes.

###### Lemma 2.4

Let $`𝒬:=\omega (𝒫)`$ be the image of a polytope $`𝒫`$ under a linear map $`\omega `$. Then every direction $`q`$ of an edge of $`Q`$ is the image under $`\omega `$ of some direction $`p`$ of an edge of $`𝒫`$.

Proof. Let $`q`$ be a direction of an edge $`[x,y]`$ of $`𝒬`$. Consider the face $`F:=\omega ^1([x,y])`$ of $`𝒫`$. Let $`V`$ be the set of vertices of $`F`$ and let $`U=\{uV:\omega (u)=x\}`$; as $`xy`$, $`UV`$. Further, as the graph of $`F`$ is connected there must be an edge $`[u,v]`$ of $`F`$, and hence of $`𝒫`$, for some $`uU`$ and $`vVU`$. Then $`\omega (v)(x,y]`$ hence $`\omega (v)=x+\alpha q`$ for some $`\alpha 0`$. Therefore $`q=\frac{1}{\alpha }(\omega (v)\omega (u))=\omega (\frac{1}{\alpha }(vu))=\omega (p)`$ with $`p:=\frac{1}{\alpha }(vu)`$, a direction of the edge $`[u,v]`$ of $`𝒫`$.

### 2.2 Reduction of convex to linear combinatorial optimization

We now reduce convex to linear combinatorial optimization. We make the following assumptions. The ground set is $`N:=\{1,\mathrm{},n\}`$ and the family $`2^N`$ is edge-guaranteed, which means that it is nonempty and comes with an explicit set $`E=\{e^1,\mathrm{},e^m\}^n`$ of vectors guaranteed to contain a direction of each edge of the polytope $`𝒫^{}=\text{conv}\{\mathbf{\hspace{0.17em}1}_F:F\}`$ associated with $``$. In this subsection we assume that $``$ is presented by a linear combinatorial optimization oracle that, given $`b:N`$, returns a family member $`F`$ of maximum weight $`b(F)=_{jF}b(j)`$. The convex functional $`c:^d`$ is presented by an evaluation oracle that, given $`x^d`$, returns the value $`c(x)`$. The weighting $`w:N^d`$ is given by an explicit list $`w(1),\mathrm{},w(n)^d`$. We consider $`d`$ as fixed; otherwise, as mentioned before, the problem becomes intractable at once even for the simple family $`=2^N`$, see Example 3.1 below. The following algorithm, applied to the data above, provides a reduction of convex to linear combinatorial optimization.

###### Algorithm 2.5

Given data as above, perform the following steps:

1. Consider the linear map $`\omega :^n^d`$ defined by $`\omega (x):=_{j=1}^nw(j)x_j`$.

1. Compute the image $`\omega (E)=\{\omega (e^1),\mathrm{},\omega (e^m)\}`$ of $`E`$ under $`\omega `$.
2. Consider the zonotope $`𝒵:=\text{zone}(\omega (E))=_{i=1}^m[\omega (e^i),\omega (e^i)]`$ in $`d`$-space $`^d`$ .

1. Compute the list $`\{u^1,\mathrm{},u^k\}`$ of all vertices of $`𝒵`$.
    2. For each $`u^i`$ compute a linear functional $`a^i𝒞_𝒵^{u^i}`$ in the normal cone of $`𝒵`$ at $`u^i`$.
3. 1. For each $`a^i`$ compute $`b^i:N`$ defined by $`b^i(j):=a^iw(j)=_{t=1}^da_t^iw(j)_t`$.
    2. For each $`b^i`$ query the oracle of $``$ and obtain $`F^i`$ of maximum weight $`b^i(F^i)`$.
    3. For each $`F^i`$ query the oracle of $`c`$ and obtain the value $`c(w(F^i))=c(_{jF^i}w(j))`$.
4. Output $`F^i`$ of maximum value $`c(w(F^i))`$ among $`F^1,\mathrm{},F^k`$.

###### Theorem 2.6

Algorithm 2.5 solves the convex combinatorial optimization problem with data as above in strongly polynomial oracle time using $`O(nm^{d1})`$ arithmetic operations and $`O(m^{d1})`$ queries of the linear combinatorial optimization oracle of $``$ and the evaluation oracle of $`c`$.

Proof. First we justify the algorithm. Recall the polytope $`𝒫_w^{}=\text{conv}\{w(F):F\}`$. As

$$𝒫_w^{}=\text{conv}\{w(F):F\}=\text{conv}\{\omega (\mathrm{𝟏}_F):F\}=\omega (𝒫^{}),$$

$`𝒫_w^{}`$ is the image of $`𝒫^{}`$ under the linear map $`\omega `$ defined in step 1 of the algorithm. Thus, by Lemma 2.4, the image $`\omega (E)`$ of $`E`$ under $`\omega `$ contains a direction of every edge of $`𝒫_w^{}`$. Therefore, by Lemma 2.3, the zonotope

$$𝒵:=\text{zone}(\omega (E))=\underset{i=1}{\overset{m}{}}[\omega (e^i),\omega (e^i)]$$

defined in step 2 is a refinement of $`𝒫_w^{}`$. Now consider any vertex $`v`$ of $`𝒫_w^{}`$. Since $`𝒵`$ refines $`𝒫_w^{}`$, the normal cone of $`𝒫_w^{}`$ at $`v`$ contains the normal cone of $`𝒵`$ at some vertex $`u^i`$ of $`𝒵`$ found in step 2a. This implies that the corresponding linear functional $`a^i𝒞_𝒵^{u^i}`$ found in step 2b is maximized uniquely over $`𝒫_w^{}`$ at $`v`$. Now, consider the corresponding weighting $`b^i`$ defined in step 3a. As $`v`$ is the unique maximizer of $`a^i`$ over $`𝒫_w^{}=\text{conv}\{w(F):F\}`$, we have

$$b^i(F)=\underset{jF}{}a^iw(j)=a^i\underset{jF}{}w(j)=a^iw(F)a^iv$$

for each $`F`$, with equality if and only if $`w(F)=v`$. Thus, the member $`F^i`$ obtained in step 3b from the linear combinatorial optimization oracle of $``$ when maximizing $`b^i`$ has $`v=w(F^i)`$. It follows that every vertex of $`𝒫_w^{}`$ equals $`w(F^i)`$ for some $`F^i`$ obtained in step 3b. Since $`c`$ is convex, the maximum value $`c(w(F))`$ of $`F`$ occurs at some vertex $`v=w(F^i)`$ of $`𝒫_w^{}`$. Thus the member $`F^i`$ output by the algorithm in step 4, which has maximum value $`c(w(F^i))`$ among the values computed in step 3c, is an optimal solution to the convex combinatorial optimization problem.

Next we verify the claimed complexity, where, as explained, $`d`$ is considered fixed. The computation of the linear image $`\omega (E)`$ in step 1a takes $`O(dnm)=O(nm)`$ operations. By Lemma 2.1, the number of vertices of the zonotope $`𝒵`$ defined in step 2 satisfies $`k=O(m^{d1})`$, and the computation of these vertices $`u^i`$ and of corresponding linear functionals $`a^i`$ in steps 2a and 2b requires $`O(m^{d1})`$ operations by Lemma 2.2. The number of queries in step 3b of the oracle of $``$ and in step 3c of the oracle of $`c`$ are $`k=O(m^{d1})`$ as claimed. The computation of each $`b^i`$ in step 3a and of each $`w(F^i)`$ in step 3c take $`O(dn)=O(n)`$ operations totalling together over all $`i`$ to $`O(kn)=O(nm^{d1})`$ arithmetic operations. Finally, the arithmetic complexity of finding the maximum among the $`k`$ values $`c(w(F^i))`$ in step 4 is $`O(k)=O(m^{d1})`$. Thus, the dominant arithmetic complexity is $`O(nm^{d1})`$ as claimed.

As the proof shows, convex combinatorial optimization is solved by enumerating all vertices of the polytope $`𝒫_w^{}`$ and picking the best. While each vertex of $`𝒫_w^{}`$ is the image under $`w`$ of some vector 1F, with $`F`$, the difficulty is that the number of sets in $``$ is typically exponential in $`n`$ and hence it is generally impossible to construct $`𝒫_w^{}`$ directly in polynomial arithmetic complexity (in particular, each 1F is a vertex of $`𝒫^{}`$). The efficient construction of $`𝒫_w^{}`$ is made possible by the given set of edge-directions of $`𝒫^{}`$ and by proceeding, indirectly, through the zonotope $`𝒵`$ that refines $`𝒫_w^{}`$. While the number of vertices of $`𝒵`$ can be much larger than that of $`𝒫_w^{}`$, the vertices of $`𝒵`$ can be better controlled and this leads to the polynomial complexity bound. So if the polytope $`𝒫^{}`$ of a family $``$ admits a relatively small set containing a direction of each edge which can be efficiently constructed or even characterized, then the problem is efficiently reducible.

### 2.3 Generic solution of the linear combinatorial optimization counterparts

We now discuss how to realize an oracle that will repeatedly solve each of the linear combinatorial optimization counterparts queried upon in Algorithm 2.5. As before, we assume that our family $``$ is edge-guaranteed and hence nonempty and comes with an explicit set $`E=\{e^1,\mathrm{},e^m\}`$ containing a direction of each edge of $`𝒫^{}`$. We assume moreover that the family comes with one member $`F^0`$ to start with. We consider the following three oracle presentations of $``$.

* Membership oracle: when queried about $`FN`$, this oracle asserts whether or not $`F`$.
* Augmentation oracle: when queried about $`F`$ and $`b:N`$, this oracle returns a family member $`\widehat{F}`$ with $`b(\widehat{F})>b(F)`$ or asserts that $`F`$ has maximum weight in $``$.
* Linear combinatorial optimization oracle: when queried about $`b:N`$, this oracle returns a family member $`F`$ of maximum weight $`b(F)`$.

###### Lemma 2.7

For any edge-guaranteed family, a membership oracle enables to simulate an augmentation oracle in strongly polynomial oracle time.

Proof. Without loss of generality, assume that each $`e^i`$ is a $`\{1,0,1\}`$-vector. The simulation is simple. Consider a query about $`F`$ and $`b:N`$. Call an edge-direction $`e^i`$ improving if $`b(e^i)=_{j=1}^nb(j)e_j^i>0`$; call it admissible at $`F`$ if $`\mathrm{𝟏}_𝐅+e^i`$ is a $`\{0,1\}`$-vector whose support $`F^i:=\text{supp}(\mathrm{𝟏}_𝐅+e^i)`$ is in $``$. If there is an edge-direction $`e^i`$ which is both improving and admissible then return $`F^i`$; otherwise assert that $`F`$ has maximum weight in $``$. The simulation works correctly since, as is well known, a vertex $`u`$ is not a maximizer of a linear functional $`b`$ over a polytope if and only if the polytope has an edge $`[u,v]`$ for some vertex $`v`$ with $`b(v)>b(u)`$.

The next lemma is from ; see  for the state of the art on this line of research. It involves a computationally heavy Diophantine approximation step  and a scaling step . We include an outline of the proof, which is relevant for the discussion in the next subsection.

###### Lemma 2.8

For any family, an augmentation oracle enables to simulate a linear combinatorial optimization oracle in strongly polynomial oracle time.

Proof. We outline the simulation. Consider query about $`b:N`$. The Diophantine approximation step (see \[20, Theorem 3.3\]) replaces $`b`$ by $`a:N`$ with the following two properties: first, it is equivalent to $`b`$ in that, for any pair $`F,GN`$, it satisfies $`a(F)a(G)`$ if and only $`b(F)b(G)`$; and second, the maximum number of bits $`k:=1+\mathrm{max}_{jN}\mathrm{log}|a(j)|`$ in the binary representation of the weight under $`a`$ of any element is polynomial in $`n`$.

The scaling step (inspired by ) is the following. Applying a simple transformation (see ) we may assume $`a`$ is nonnegative. Following the prof of \[24, Theorem 9.2\], for $`i=0,\mathrm{},k`$, starting with $`F^i`$, find a maximizing $`F^{i+1}`$ with respect to the weighting $`a^i:=2^{ik}a`$. As shown in  or , each $`F^{i+1}`$ is obtained from $`F^i`$ by calling the augmentation oracle at most $`n`$ times. Thus, the maximizer $`F^{k+1}`$ of $`a=a^k`$ is found using at most $`kn`$ calls, and since $`k`$ is polynomial in $`n`$, the desired maximizer of $`b`$ is obtained in strongly polynomial oracle time.

We can now prove Theorem 1.1. As discussed before, the family $`2^N`$ comes with one explicit $`F^0`$ and an explicit set $`E=\{e^1,\mathrm{},e^m\}^n`$ containing a direction of each edge of $`𝒫^{}`$, and is presented by a membership oracle. The complexity is measured in terms of $`n`$ and $`m`$.

Theorem 1.1 For any fixed $`d`$, there is a strongly polynomial oracle time algorithm solving convex combinatorial optimization over any edge-guaranteed family presented by a membership oracle.

Proof. Theorem 2.6 guarantees that Algorithm 2.5 solves the convex combinatorial optimization problem over $``$ efficiently using a linear combinatorial optimization oracle which, by Lemmas 2.7 and 2.8, can be efficiently simulated from the membership oracle presenting $``$.

We conclude this subsection with several important remarks which lead to the discussion in the next subsection. First, the complexity behind Theorem 1.1 is quite horrendous: for each linear combinatorial optimization counterpart invoked by Algorithm 2.5, an application of the Diophantine approximation step which takes $`O(n^8)`$ arithmetic operations  is required. However, improved complexity bounds follow from Theorem 2.6 when Algorithm 2.5 is used with a more efficient linear combinatorial optimization oracle whenever a particular family admits one.

Second, what about real data and real arithmetic computation (where pairs of real numbers can be added, multiplied or compared in unit time)? Algorithm 2.5 remains valid and polynomial and the analog of Theorem 2.6 (with “strongly polynomial oracle time” replaced by “polynomially many real arithmetic operations and queries”) holds. So does the conversion of the membership oracle to the augmentation oracle manifested by Lemma 2.7 above. However, the proof of both parts of Lemma 2.8 (scaling and Diophantine approximation) breaks down for real data, and the conversion of the augmentation oracle to the optimization oracle is no longer available.

Can these obstacles be waved and does the real analog of Theorem 1.1 remain valid? Our families are edge-guaranteed, which is stronger than having a test set (see  and references therein) and even more so than having a mere augmentation oracle: can we take advantage of that and simulate standard linear combinatorial optimization directly and more efficiently, avoiding scaling and Diophantine approximation? We discuss some of these issues next.

### 2.4 On the Hirsch conjecture and the Klee-Minty problem for $`(0,1)`$-polytopes

A form of the Hirsch conjecture, open to date, asks whether the diameter of (the graph of) every $`n`$-polytope with $`f`$ facets is bounded above by a polynomial in $`n`$ and $`f`$; for all one knows, the linear upper bound $`fn`$ may suffice, see . Also open is the analogous form of the monotone Hirsch conjecture asking whether the shortest increasing path under any linear functional from any vertex to some maximizing vertex is polynomially bounded in $`n`$ and $`f`$. Both variants are true for $`(0,1)`$-polytopes  as well as for some more general classes of integer polytopes . The following slightly stronger form, relevant to the discussion below, holds.

###### Lemma 2.9

Any $`(0,1)`$ $`n`$-polytope $`P`$ admits, under any linear functional, a nondecreasing path from any vertex $`u`$ to any maximizing vertex $`w`$, of length at most $`n`$ using no edge-direction twice.

Proof. The claim being trivial for $`n=0`$, we proceed by induction. If $`u`$ and $`w`$ lie on a common proper face of $`P`$ then induction takes over. Otherwise, there is a nondecreasing arc $`(u,v)`$; pick any $`i`$ with $`u_iv_i`$; then $`v_i=w_i`$ and hence, by induction, there is a nondecreasing $`(v,w)`$-path of length at most $`n1`$ using no edge-direction twice on the face $`F:=\{xP:x_i=w_i\}`$. As no edge of $`F`$ can have direction $`vu`$, this path preceded by the arc $`(u,v)`$ gives the desired $`(u,w)`$-path.

The effective Hirsch conjecture asks, broadly, whether a monotone path could be efficiently traced. To make things precise, the presentation of the polytope has to be specified. For instance, tracing such a path in strongly polynomial time for polytopes presented by linear inequalities would imply a strongly polynomial time algorithm for linear programming via the simplex method which does not seem likely; but tracing it in subexponential time is possible . A natural question is: how long can an arbitrary increasing path be? A classical construction by Klee and Minty  transforms the $`n`$-cube so as to admit increasing paths of exponential length $`2^n`$. But $`(0,1)`$-polytopes are very special, as shows Lemma 2.9. How long, then, can an arbitrary increasing path in a $`(0,1)`$-polytope be? We now show that, unfortunately, $`(0,1)`$-polytopes admit such paths of length exponential in the dimension as well: in this sense, the following lemma can be regarded as a $`(0,1)`$ analog of the Klee-Minty cube; we thank Tal Raviv for a related discussion.

###### Lemma 2.10

For every $`n`$ there is a $`(0,1)`$-polytope of dimension less than $`\frac{1}{4}n^4`$ with $`n!`$ vertices that admits a Hamiltonian (and hence $`n!`$-long) nondecreasing path under every linear functional.

Proof. The Young polytope $`Y_{n2,2}`$ is the convex hull of all $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)\times \left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ matrices of permutations of edges of the complete graph $`K_n`$ induced by the $`n!`$ permutations of its vertices. For instance, the matrix corresponding to the permutation of vertices $`\sigma =(1,2,3,4)`$ (in cycle notation) is

$$\mathrm{\Sigma }=\begin{array}{ccccccccc}& & 12& 13& 14& 23& 24& 34& \\ 12& (\mathrm{}& 0& 0& 0& 1& 0& 0& )\mathrm{}\\ 13& 0& 0& 0& 0& 1& 0\\ 14& 1& 0& 0& 0& 0& 0\\ 23& 0& 0& 0& 0& 0& 1\\ 24& 0& 1& 0& 0& 0& 0\\ 34& 0& 0& 1& 0& 0& 0\end{array}.$$

The claims about the dimension and number of vertices of $`Y_{n2,2}`$ are obvious. In  it was shown that $`Y_{n2,2}`$ is $`2`$-neighborly, that is, its graph is the complete graph $`K_{n!}`$: the very existence of $`2`$-neighborly $`(0,1)`$-polytopes is an amazing fact in itself! It follows that if $`a`$ is any linear functional, then any ordering $`v_1,\mathrm{},v_{n!}`$ of the vertices of $`Y_{n2,2}`$ satisfying $`a(v_1)\mathrm{}a(v_{n!})`$ gives a Hamiltonian (and hence exponentially long) nondecreasing path under $`a`$.

Here, however, we are especially interested in the polytopes $`𝒫^{}`$ of edge-guaranteed families. Lemmas 2.7 and 2.8 imply that for such a family, a monotone path can be traced in time strongly polynomial in $`m`$ and $`n`$, alas, for rational functionals only, and using the heavy Diophantine approximation procedure. Can we do better? what is the maximal length $`I(n,m)`$ of any increasing path in any $`n`$-dimensional $`(0,1)`$-polytope with $`m`$ pairwise nonproportional edge-directions?

### 2.5 Edge-well-behaved classes

In most applications, in particular all of those discussed in Section 3, one is concerned with a class of families possessing some unifying structure. It is therefore useful to make some formal definitions regarding such classes and then use it to obtain a suitable corollary of Theorem 1.1. For $`n0`$ let $`N=\{1,\mathrm{},n\}`$ as before and let $`𝒰_n`$ be the set of all families with ground set $`N`$,

$$𝒰_n:=2^{2^{\{1,\mathrm{},n\}}}=\{:2^N\}.$$

A class of families is a (typically infinite) set of families $`𝒞=_{n0}𝒞_n`$ with $`𝒞_n𝒰_n`$ for all $`n`$.

###### Definition 2.11

A class $`𝒞`$ is edge-well-behaved if there is a polynomial time algorithm that, given $`n`$, produces a set $`E_n=\{e^1,\mathrm{},e^{m(n)}\}\{1,0,1\}^n`$ with respect to which every $`𝒞_n`$ is edge-guaranteed. In particular, $`m(n)`$ is polynomial in $`n`$ and each $`𝒞`$ is nonempty.

While the existence of such a “uniform” polynomial time algorithm that produces sets containing edge-directions for the polytopes of all families in the class may seem a strong assumption, we will see in Section 3 that in many applications such an algorithm is readily available. Also, the assumption that the edge-directions are $`(1,0,1)`$-valued is not restrictive since, for $`(0,1)`$-polytopes, each edge is a difference of two vertices hence admits a $`(1,0,1)`$-direction. The next corollary follows at once from Theorem 1.1; here the complexity is in terms of $`n`$ only.

###### Corollary 2.12

Fix any $`d`$. Then for any edge-well-behaved class there is a strongly polynomial oracle time algorithm that solves the convex combinatorial optimization problem over any family in the class which is presented by a membership oracle.

While this statement may seem a reformulation of Theorem 1.1, it is natural and useful in uniformly establishing the polynomial solvability in all of the applications discussed in Section 3.

### 2.6 Projection representation and circuits

We conclude Section 2 by discussing a useful setup that helps in controlling edge-directions, and which is used and demonstrated in the application given in §3.2 in the sequel. A circuit of an $`r\times s`$ matrix $`A`$ is a nonzero solution $`z^s`$ of the system $`Az=0`$ whose support is inclusion-minimal. It is known (cf. \[43, Exercise 10.14\]) that any nonzero solution of $`Az=0`$ has a conformal circuit decomposition, i.e. can be expressed as $`z=_i\alpha _iz^i`$ with the $`\alpha _i`$ positive scalars and the $`z^i`$ pairwise nonproportional circuits such that $`z_j^iz_j>0`$ for all $`i`$ and all $`j\text{supp}(z^i)`$. Consider the standard polytope $`𝒫=\{x^s:Ax=b,lxu\}`$ defined by $`A`$, right-hand side $`b^r`$, lower bound $`l^s`$, and upper bound $`u^s`$. We provide a short proof of the following useful property of edge-directions of the standard polytope (see  for a refinement of this property which characterizes edge-directions).

###### Lemma 2.13

Each edge-direction of a standard $`𝒫`$ is a circuit of its defining matrix $`A`$.

Proof. Consider any $`x,y𝒫`$. Then $`A(yx)=0`$ so $`yx`$ admits a conformal circuit decomposition $`yx=_i\alpha _iz^i`$. It is then not hard to verify that for every circuit $`z^i`$ participating in that decomposition, both $`x+\alpha _iz^i`$ and $`y\alpha _iz^i`$ satisfy the lower and upper bounds and hence are in $`𝒫`$. They belong, moreover, to any face $`F`$ containing both $`x`$ and $`y`$. Indeed, pick any $`c`$ in the normal cone $`𝒞_𝒫^F`$: then $`cxc(x+\alpha _iz^i)`$ which implies $`cz^i0`$, and $`cyc(y\alpha _iz^i)`$ which implies $`cz^i0`$. It follows that $`cz^i=0`$ and hence $`c(x+\alpha _iz^i)=cx`$ and $`c(y\alpha _iz^i)=cy`$ implying $`x+\alpha _iz^i,y\alpha _iz^iF`$. Now, if the decomposition $`yx=_i\alpha _iz^i`$ involves more than one circuit, say $`z^1,z^2`$, then any face containing $`x,y`$ contains the three non-collinear points $`x,x+\alpha _1z^1,x+\alpha _2z^2`$ and hence is not an edge. So if $`[x,y]`$ is an edge of $`𝒫`$ then $`yx=\alpha z`$ for some circuit $`z`$. Any direction of that edge is a nonzero multiple of $`z`$ and hence a circuit of $`A`$.

Lemma 2.13 implies that any inclusion-maximal set $`Z`$ of pairwise nonproportional circuits of $`A`$ contains a direction of each edge of $`𝒫`$. So if the size of $`A`$ is $`r\times s`$ then $`𝒫`$ admits such a set $`Z`$ with no more than $`\left(\genfrac{}{}{0pt}{}{s}{r}\right)`$ elements. Every polytope $`𝒬`$ is the linear image of a standard polytope: if $`𝒬=\{x:Bxb\}`$ is a description by inequalities then, adding a suitable “slack” vector $`y`$, we get $`𝒬=\varphi (𝒫)`$ with $`𝒫=\{(x,y):Bx+Iy=b,y0\}`$ and with $`\varphi `$ the “$`y`$ forgetting” projection $`\varphi (x,y)=x`$. In particular, the polytope $`𝒫^{}`$ of any family $``$ is the linear image $`𝒫^{}=\varphi (𝒫)`$ of a standard polytope $`𝒫=\{x^s:Ax=b,lxu\}`$. Typically the number of inequalities describing $`𝒫^{}`$ is exponentially large and hence so is the dimension of $`𝒫`$, but when $`𝒫`$ has small dimension, we can benefit from such a “projection representation” in two ways as follows.

First, if the defining matrix $`A`$ admits an efficiently determinable set $`Z=\{z^1,\mathrm{},z^m\}^s`$ containing a scalar multiple of each circuit of $`A`$ then, by Lemmas 2.4 and 2.13, its image $`E:=\varphi (Z)`$ contains a direction of each edge of $`𝒫^{}`$, making $``$ an edge-guaranteed family. Second, linear combinatorial optimization over $``$ can be “lifted” to linear programming over the polytope $`𝒫`$, giving a way alternative to §2.3 for solving the counterparts called upon by Algorithm 2.5.

## 3 Some Applications

### 3.1 Some direct applications

Here we give two examples where the set of edge-directions can be directly determined and used.

###### Example 3.1

Positive semidefinite quadratic assignment. The quadratic assignment problem is the following: given a real $`n\times n`$ matrix $`M`$, find $`x\{0,1\}^n`$ maximizing the quadratic form $`x^TMx`$ induced by $`M`$; see  for an overview of this problem and its applications. We consider the instance where $`M`$ is positive semidefinite, in which case it can be assumed to be presented as $`M=W^TW`$ with $`W`$ a given $`d\times n`$ matrix. If the rank $`d`$ of $`W`$ and $`M`$ is variable then this problem is NP-hard . For fixed $`d`$ it is polynomial time solvable .

When $`W`$ is rational, the problem can be modelled as convex combinatorial optimization with the following data: the family is the entire power set $`=2^N`$ of $`N`$ with the natural correspondence $`\{0,1\}^n`$; the weight of $`jN`$ is the $`j`$th column $`w(j):=W^j`$ of the matrix $`W`$; and $`c:^d:xx^2`$ is the squared standard $`l_2`$ norm. Indeed, for each $`F`$ we then have $`\mathrm{𝟏}_F^TW^TW\mathrm{𝟏}_F=c(w(F))`$.

Now, the polytope of the family $``$ here is just the $`n`$-cube $`𝒫^{}=[0,1]^n`$; therefore the trivially computable set of $`n`$ standard unit vectors $`E:=\{\mathrm{𝟏}_1,\mathrm{},\mathrm{𝟏}_n\}`$ contains a direction of each edge. Thus, the class of all such families is edge-well-behaved with $`m(n)=n`$ and Corollary 2.12 applies and guarantees the efficient solution. Here, one obtains a faster solution by using Algorithm 2.5 together with a linear combinatorial optimization oracle realized by simple sign checking as follows: given $`b:N`$, a member $`F`$ maximizing $`b(F)`$ is simply $`F:=\{j:b(j)>0\}`$.

###### Example 3.2

Convex matroid optimization. This problem is the special case of convex combinatorial optimization where $``$ is either the collection $``$ of bases (considered in ) or the collection $``$ of independent sets of a matroid over $`N`$. It generalizes classical matroid optimization, first studied in , and has a rich modelling power on its own: useful matroids include the forest matroid of a graph and, more generally, the matroid of linear dependencies of a matrix over a field. For us here it suffices that the matroid is presented by a membership oracle for $``$.

It can be derived from the matroid-bases-axioms that the trivially computable set $`D:=\{\mathrm{𝟏}_i\mathrm{𝟏}_j:\mathrm{\hspace{0.17em}1}i<jn\}`$ of $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ differences of unit vectors contains a direction of each edge of the polytope $`𝒫^{}`$ of the family $``$ of bases. Likewise, it can be derived from the matroid-independence-axioms that the $`\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)`$-element union $`DE`$ of $`D`$ and the set $`E:=\{\mathrm{𝟏}_1,\mathrm{},\mathrm{𝟏}_n\}`$ of unit vectors contains a direction of each edge of the polytope $`𝒫^{}`$ of the family $``$ of independent sets. Thus, the class of all such families $``$ (respectively, families $``$) is edge-well-behaved with $`m(n)=\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ (respectively, $`m(n)=\left(\genfrac{}{}{0pt}{}{n+1}{2}\right)`$), and Corollary 2.12 applies and guarantees the efficient solution.

Here too, one obtains a faster solution by using Algorithm 2.5 together with a linear combinatorial optimization oracle over $`=`$ or $`=`$ which is efficiently realizable from a membership oracle for $``$ using the classical greedy algorithm (cf. ) that, given $`b:N`$ makes use of sorting the values $`b(j)`$ to find the lexicographically $`b`$-largest member $`F`$ which can be shown to be the one maximizing $`b(F)`$.

### 3.2 Shaped vector partitioning

The shaped partition problem concerns the partitioning of a multiset $`V=\{v^1,\mathrm{},v^n\}`$ of $`n`$ vectors in $`d`$-space into $`p`$ parts so as to maximize an objective function which is convex on the sum of vectors in each part, subject to constraints on the number of elements in each part. To describe the problem precisely we need some notation. A $`p`$-partition of the index set $`\{1,\mathrm{},n\}`$ of $`V`$ is an ordered tuple $`\pi =(\pi _1,\mathrm{},\pi _p)`$ of pairwise disjoint sets whose union is $`\{1,\mathrm{},n\}`$. The shape of a partition is the tuple of cardinalities of its parts, $`|\pi |:=(|\pi _1|,\mathrm{},|\pi _p|)`$. In addition to the set of vectors $`V`$, the data includes vectors $`l,u\{0,1\mathrm{},n\}^p`$ with $`lu`$ providing lower and upper bounds on the shape of admissible partitions. With each partition $`\pi `$ is associated a $`d\times p`$ matrix

$$V^\pi :=[\left(\underset{i\pi _1}{}v^i\right),\mathrm{},\left(\underset{i\pi _p}{}v^i\right)]=\underset{j=1}{\overset{p}{}}\left(\underset{i\pi _j}{}v^i\right)\mathrm{𝟏}_j^T$$

whose $`j`$th column is the sum (representing the “total value”) of vectors assigned to the $`j`$th part. The data also includes a convex functional $`c:^{d\times p}`$ on $`d\times p`$ matrices which “weighs together” the sums of vectors in the various parts. The problem is to find a $`p`$-partition $`\pi `$ whose shape satisfies the lower and upper bounds $`l|\pi |u`$ and which maximizes the value $`c(V^\pi )`$.

Shaped partition problems have applications in diverse fields such as clustering, inventory, reliability, and more - see  and references therein. Here is a typical example.

###### Example 3.3

Minimal variance clustering. This is the following problem, which has numerous applications in the analysis of statistical data: given $`n`$ sample points $`v^1,\mathrm{},v^n`$ in $`d`$-space, group the points into $`p`$ clusters $`\pi _1,\mathrm{},\pi _p`$ so as to minimize the sum of cluster variances

$$\underset{j=1}{\overset{p}{}}\frac{1}{|\pi _j|}\underset{i\pi _j}{}v^i(\frac{1}{|\pi _j|}\underset{i\pi _j}{}v^i)^2.$$

We consider the instance where there are $`n=pm`$ points and the clustering sought is balanced, that is, the clusters should have equal size $`m`$. Suitable manipulation of the sum of variances shows that the problem is equivalent to a shaped partition problem with the lower and upper bounds $`l:=u:=(m,\mathrm{},m)`$ (forcing the single shape $`|\pi |=(m,\mathrm{},m)`$ on partitions), and with the convex functional (to be maximized) simply as the square of the $`l_2`$ norm on $`d\times p`$ matrices, given by $`c:^{d\times p}:XX^2=_{i=1}^d_{j=1}^p|X_{i,j}|^2`$.

If either the dimension $`d`$ or the number of parts $`p`$ is variable, the shaped partition problem instantly captures NP-hard problems hence is presumably intractable . Therefore, it is interesting to study the worst case arithmetic complexity in terms of the number $`n`$ of points with both $`d,p`$ fixed. In the special case where there are no shape restrictions (partitions of all shapes are admissible), an upper bound of $`O(n^{d(p1)1})`$ on the complexity is given in  and a quite compatible lower bound of $`\mathrm{\Omega }(n^{\frac{d1}{2}p})`$ is in . In the more general case where arbitrary sets of shapes are allowed, the best upper bound to date is $`O(n^{dp^2})`$ from ; while a matching lower bound is unknown, the lower bound $`O(n^{d\left(\genfrac{}{}{0pt}{}{p}{2}\right)})`$ from  on the related number of separable partitions indicates that the quadratic term $`p^2`$ in the exponent may be unavoidable.

We now show how to solve the shaped partition problem efficiently using our framework. We begin by modelling it as a convex combinatorial optimization problem. The ground set is taken to be $`N:=\{(i,j):\mathrm{\hspace{0.17em}1}in,1jp\}`$. Each $`p`$-partition $`\pi =(\pi _1,\mathrm{},\pi _p)`$ is encoded as the set $`F_\pi :=\{(i,j):i\pi _j\}N`$. The family consists of all such sets corresponding to $`p`$-partitions of admissible shapes, $`:=\{F_\pi :l|\pi |u\}`$. The weight of element $`(i,j)N`$ is the $`d\times p`$ matrix $`w(i,j):=v^i\mathrm{𝟏}_j^T`$ whose $`j`$th column is $`v^i`$ and whose other columns are zero. Finally, the convex functional is simply the given one $`c`$ defined on $`d\times p`$ matrix space. It is not hard to verify that this indeed casts the shaped partition problem as a convex combinatorial optimization problem with a ground set of size $`|N|=np`$ and weight vectors (matrices) in dimension $`dp`$.

To show that the class of all such families is edge-well-behaved we discuss the family polytope $`𝒫^{}^{n\times p}`$. The indicator of a family member $`F_\pi `$ is the $`(0,1)`$-valued $`n\times p`$ matrix $`\mathrm{𝟏}_\pi `$ whose $`(i,j)`$th entry equals $`1`$ precisely when $`i\pi _j`$. The polytope $`𝒫^{}`$ admits a simple projection-representation as follows. Consider $`(n+1)\times p`$ matrices whose rows are indexed by $`\{0,1,\mathrm{},n\}`$. Define lower and upper bound matrices $`L,U`$ in terms of the given vectors $`l,u`$ as follows: for $`j=1,\mathrm{},p`$ set $`L_{i,j}:=0,U_{i,j}:=1`$ if $`1in`$ and $`L_{0,j}:=nu_j,U_{0,j}:=nl_j`$. Let $`𝒫`$ be the transportation polytope defined by this data, which is the following standard polytope

$$𝒫:=\{X^{(n+1)\times p}:\underset{j=1}{\overset{p}{}}X_{i,j}=1(1in),\underset{i=0}{\overset{n}{}}X_{i,j}=n(1jp),LXU\}.$$

Then $`𝒫^{}=\varphi (𝒫)`$ with $`\varphi :^{(n+1)\times p}^{n\times p}`$ the projection erasing the $`0`$th row of a matrix.

Let $`K_{n+1,p}`$ be the complete bipartite graph with edge set $`\{(i,j):\mathrm{\hspace{0.17em}0}in,1jp\}`$ corresponding to this transportation system. Each circuit of $`K_{n+1,p}`$ gives an $`(n+1)\times p`$ matrix supported on that circuit, with values $`\pm 1`$ alternating along the edges of the circuit and $`0`$ elsewhere. It is well known that each circuit of the $`(n+p)\times (n+1)p`$ matrix of coefficients of the equation system defining $`𝒫`$ is proportional to some such circuit-supported matrix. Let $`Z:=\{z^1,\mathrm{},z^m\}`$ be the set of all such $`(n+1)\times p`$ matrices corresponding to the $`m:=_{i=2}^p\frac{1}{2}\left(\genfrac{}{}{0pt}{}{p}{i}\right)\left(\genfrac{}{}{0pt}{}{n+1}{i}\right)i!(i1)!`$ distinct circuits of $`K_{n+1,p}`$. Then the projection $`E=\{e^1,\mathrm{},e^m\}:=\varphi (Z)`$ is a set of $`(1,0,1)`$-valued $`n\times p`$ matrices which, as explained in §2.6, contains a direction of each edge of $`𝒫^{}`$.

Since $`p`$ is assumed to be fixed, the set of circuits $`Z`$ and its projection $`E`$ are computable in time polynomial in $`n`$, and therefore the class of all such families is indeed edge-well-behaved with $`m(n)=_{i=2}^p\frac{1}{2}\left(\genfrac{}{}{0pt}{}{p}{i}\right)\left(\genfrac{}{}{0pt}{}{n+1}{i}\right)i!(i1)!=O(n^p)`$. Thus, Corollary 2.12 applies and guarantees the efficient solution. As in the examples in §3.1, here too one can obtain a typically faster solution by using Algorithm 2.5 together with a linear combinatorial optimization oracle realized by lifting to $`𝒫`$ and solving the corresponding transportation problem using available fast algorithms for bipartite network flows, see . These algorithms, however, are not strongly polynomial and do depend on the bit size of the bounds $`l,u`$ and the costs $`b^i`$ called repeatedly by Algorithm 2.5.

For unrestricted partitioning, that is, shaped partitioning with $`l=(0,\mathrm{},0)`$ and $`u=(n,\mathrm{},n)`$, the characterization of circuits obtained in  shows that circuits of $`K_{n+1,p}`$ which yield circuits of the matrix of coefficients of the equation system defining $`𝒫`$ correspond to switching a single item from one part to another. As the number of such circuits is $`n\left(\genfrac{}{}{0pt}{}{p}{2}\right)`$, the class of such families is edge-well-behaved with (improved) $`m(n)=n\left(\genfrac{}{}{0pt}{}{p}{2}\right)`$. Thus, while Theorem 2.6 with $`m(n)=O(n^p)`$ and dimension $`dp`$ implies a complexity bound of $`n^{O(dp^2)}`$ on the general shaped partition problem, in line with , with $`m(n)=n\left(\genfrac{}{}{0pt}{}{p}{2}\right)`$ and same dimension $`dp`$ it implies the improved bound of $`n^{O(dp)}`$ on the complexity of the unrestricted partition problem, in line with .

## 4 Concluding Remarks

In this article we have defined the convex combinatorial optimization problem and shown that it can be solved in strongly polynomial time for edge-guaranteed families and for edge-well-behaved classes of families. We have demonstrated several natural and broad applications that indeed give rise to edge-well-behaved classes and therefore are efficiently solvable through our framework.

The polynomial time solvability of linear combinatorial optimization for facet-well-behaved classes via the Ellipsoid method  has stimulated over the years a broad body of work on the identification and characterization of such classes. A major research program called upon by this paper is an analogous identification and characterization of edge-well-behaved classes of combinatorial families, for which our framework automatically yields strongly polynomial time solvability of convex combinatorial optimization.

Some more specific questions are discussed within the body of our paper, in particular, those in §2.3 and §2.4 concerning a more efficient generic solution of standard linear combinatorial optimization over edge-guaranteed families and the effective Hirsch conjecture for polytopes of such families. What is the maximal length $`I(n,m)`$ of any increasing path in any $`n`$-dimensional $`(0,1)`$-polytope with $`m`$ pairwise nonproportional edge-directions? Can we trace such a path efficiently while avoiding scaling and the heavy Diophantine approximation procedure? Can we trace such a path in polynomially many real arithmetic operations for real linear functionals?

For solving the standard linear counterparts of a convex combinatorial optimization problem over a family $``$ with weighting $`w`$, one approach may be to try and augment along edges of the polytope $`𝒫_w^{}`$ downstairs (see discussion following the proof of Theorem 2.6). While a set of edge-directions of that polytope is available as the projection $`\omega (E)`$ of the set of edge-directions of $`𝒫^{}`$, this information is not enough: one needs to know, at any vertex $`v`$ of $`𝒫_w^{}`$, which edge-directions $`\omega (e^i)`$ are admissible at $`v`$, and moreover \- “how much to walk” - namely, what is the nonnegative scalar $`\alpha `$ such that $`v+\alpha e^i`$ is the new vertex to move to. When this information is available, even in an abstract setting of a suitably defined neighborhood oracle, it may be possible to apply the vertex enumeration methodology of ; and in some applications, such as unrestricted vector partitioning, this can be carried out particularly efficiently as in .

Finally, as mentioned in the introduction, there is much room for the study of approximation algorithms for the often intractable convex combinatorial optimization problem for various classes of families, and we hope this article will stimulate research on this yet unexplored ground.

## Acknowledgement

The first author is indebted to Lou Billera for introducing him to the theory of convex polytopes.

Shmuel Onn
*Technion - Israel Institute of Technology, 32000 Haifa, Israel*

*email: onn@ie.technion.ac.il*

*http://ie.technion.ac.il/$``$onn*

Uriel G. Rothblum
*Technion - Israel Institute of Technology, 32000 Haifa, Israel*

*email: rothblum@ie.technion.ac.il*

*http://ie.technion.ac.il/rothblum.phtml*