text:
# Hyper- and suspended-accretion states of rotating black holes and the durations of gamma-ray bursts

## 1 Introduction

Active black holes are believed to be surrounded by magnetized disks or tori. In particular, such systems are the most favorable inner engines of cosmological gamma-ray bursts. The BATSE catalogue shows a broad, bimodal distribution of GRB durations ($`T_{90}`$) centered on short bursts of $`0.3\mathrm{s}`$ and long bursts of $`30\mathrm{s}`$ (Kouveliotou et al., 1993; Paciesas et al., 1999). The cosmological origin of GRBs and their rapid variability indicate an association with stellar-mass progenitors (Woosley, 1993; Paczyński, 1991, 1997, 1998; Fryer et al., 1999). Proposed scenarios include coalescence of compact object binaries (Paczyński, 1991), and core-collapse of massive stars (Woosley, 1993). Both scenarios involve a black hole-disk or -torus system. This disk will be magnetized, due to seeding from the progenitor’s magnetic flux and disk dynamo amplification (Narayan, Paczyński, & Piran, 1992; Paczyński, 1997; Brandenburg et al., 1995; Hawley, Gammie, & Balbus, 1996; Hawley, 2000). Various lines of observational evidence support the collapsar scenario, at least for long bursts (e.g. van Putten (2001)); here, we shall suggest that both short and long bursts can be explained in a unified model with durations extended by coupling to a high-spin black hole.

Accretion provides a definite power source for GRBs, but the black hole’s spin energy, e.g., $`2M_{}c^2`$ for a $`7M_{}`$ black hole, can be at least as important. Efficient spin energy extraction requires an external magnetic field supported by surrounding matter. Magnetically mediated energy extraction mechanisms include radiation in DC Alfvén waves (Blandford & Znajek (1977); Thorne et al. (1986); see also e.g. Lee et al. (1999); Beskin & Kuznetsova (2000); Krolik (2000)), or superradiant scattering of fast magnetosonic waves (Uchida, 1997; van Putten, 1999).

The evolution of the disk or torus surrounding a black hole depends crucially on magnetic torques. Negative torques are expected from magnetic winds, which can dramatically stimulate accretion rates (e.g., Blandford & Payne (1982); Lee & Kim (2000)). Positive torques $`T=\dot{J}_H`$ may derive from coupling to the black hole’s angular momentum $`J_H`$ by equivalence in poloidal topology to pulsar magnetospheres (van Putten (1999); Brown et al. (2001)), and may be key to driving hypernovae (Brown et al., 2000). The disk may also redistribute its mass and angular momentum via internal, turbulent, magnetic and Reynolds stresses (Balbus & Hawley, 1998). The relative contributions from external (wind/black hole) stresses vs. internal stresses is presently unknown, and may depend crucially on the net poloidal flux introduced to the disk (see e.g. Matsumoto (1999)).

In this work, we focus on the duration of magnetized accretion regulated by external torques. We show that wind torques alone drive the disk to a finite-time collapse singularity. The additional positive torque from the black hole, when its angular velocity exceeds a critical value, may arrest accretion onto the black hole for the duration of its spin-down lifetime. This introduces two cases: a short-lived state of “hyperaccretion” for low-spin black holes, and a long-lived state of “suspended-accretion” for high-spin black holes. The respective time-scales are consistent with the bimodal distribution in GRB durations for plausible values of two presently-uncertain ratios: the kinetic-to-poloidal-magnetic energy in the disk and the black hole-to-disk mass. Numerical simulations soon within reach may establish the likely ranges of these ratios.

Previously, bimodality in GRB durations has been attributed to, e.g., hydrodynamic time-scales in Newtonian vs. relativistic reverse shocks in shells decelerating in the ISM (Sari & Piran, 1995), or formation of millisecond pulsars spinning above or below a gravitationally unstable limit (Yi & Blackman, 1998). Previous studies of Poynting dominated winds in GRBs have focused on plasma processes and possible connections to gamma-ray emission (e.g. Usov (1992, 1994); Mészáros & Rees (1997);Blackman & Yi (1998);Lyutikov & Blackman (2001)).

## 2 Orbital evolution of rotating, magnetized rings subject to wind torques

Magnetic disk-winds transport angular momentum by Reynolds and Maxwell stresses, which for outgoing (ingoing) flows have the same (opposite) sign. A force-free limit is defined by neglecting Reynolds stresses. Applied to outgoing winds, Maxwell stresses $`RB_rB_\varphi /4\pi `$ provide a lower limit on the disk’s accretion rate, where $`B`$ denotes the magnetic field with components in spherical coordinates $`(r,\theta ,\varphi )`$, and $`R=r\mathrm{sin}\theta `$. The force-free limit represents pure “magnetic braking.”

A magnetized disk ring, with mass $`\delta M`$ and radius $``$ in quasi-Keplerian rotation at rate $`\mathrm{\Omega }=(GM_H/^3)^{1/2}`$, evolves as it sheds angular momentum in a wind. Assuming radially asymptotic flow, the magnetic torque $`\delta \tau _B`$ on the ring equals (Goldreich & Julian, 1969):

$$\delta \tau _B=\frac{\mathrm{\Omega }}{c}\mathrm{sin}^2\theta \left(_\mu A_\varphi \right)\delta A_\varphi .$$
(1)
Here, $`\mu =\mathrm{cos}\theta `$, the poloidal magnetic field is $`B_r=r^2_\mu A_\varphi `$, and $`2\pi \delta A_\varphi `$ is the magnetic flux through the ring. The toroidal field is $`B_\varphi =\mathrm{\Omega }RB_r/c`$ (see the wind asymptotics of Goldreich & Julian (1969); Michel (1969) for aligned rotators; for disk winds, see Blandford (1976); Lee & Kim (2000)). The ring evolution equation, $`\delta \tau _B=(1/2)\mathrm{\Omega }\dot{}\delta M`$, yields

$$\dot{}=\frac{2}{c}\mathrm{sin}^2\theta \left(_\mu A_\varphi \right)\left(\frac{\delta A_\varphi }{\delta M}\right).$$
(2)
The evolution of a collapsing ring depends on its degree of magnetization and the magnetic wind’s geometry. A split-monopole geometry (SMG) for the asymptotic poloidal field is a good approximation when $`|B_r|/|B_\varphi |>>1`$, true at the onset of accretion for modest rotation rates. As the disk collapses and spins up, however, magnetic field line winding produces large toroidal magnetic fields, and a force-free-toroidal-field geometry (TFG) becomes more appropriate. SMG/TFG represent two limiting cases, for which simple solutions to equation (2) may be obtained. 111Although, as shown by Blandford & Payne (1982) for (baryonic) MHD disk winds, field line focusing may produce nonradial asymptotic poloidal fields, cylindrically-collimated MHD winds have been found to have relatively low asymptotic flow speeds (Ostriker, 1997).

Solution for split-monopole geometry — In SMG, we have $`A_\varphi =A(1\mu /\mu _0)`$, with $`\theta _0=\mathrm{arccos}(\mu _0)`$ the angle of the innermost streamline with respect to the pole; the outermost streamline lies on the equator. With $`\varpi /_0`$, for $`_0`$ the the initial ring radius, the solution of equation (2) describes a finite-time singularity:

$`\varpi (t;A_\varphi )=\left(1t/t_f^{smg}\right)^{1/2},`$ (3)
where $`t_f^{smg}=(1/4)(\delta J^0/|\delta \tau _B^0|)`$, and $`\delta J^0=\delta M\mathrm{\Omega }_0_0^2`$ and $`\delta \tau _B^0`$ denote the initial ring angular momentum and torque.

The initial ring kinetic energy is $`\delta E_k^0=\mathrm{\Omega }_0\delta J^0/2`$. The energy in the magnetic field of a (double) wedge-shaped portion $`\delta A_\varphi `$ rooted at $`_0`$ is $`\delta E_B^0=(1/2)B_r^2𝑑\mu r^2𝑑r=\delta A_\varphi |_\mu A_\varphi |/(2_0)=|\delta \tau _B|c(2_0\mathrm{\Omega }_0)^1(\mathrm{sin}\theta )^2`$. For split-monopole geometry, $`\delta E_B^0\delta E_{B,s}^0A\delta A_\varphi /(2_0)`$. The initial freefall time is $`t_{ff}=\pi /(\mathrm{\Omega }_02\sqrt{2})`$. For $`R_s2GM_H/c^2`$ the Schwarzschild radius of the black hole, the collapse time in SMG becomes

$$t_f^{smg}=\frac{1}{2cR_s}\frac{_0^2}{\mathrm{sin}^2\theta }\frac{\delta E_k}{\delta E_{B,s}}=\frac{t_{ff}/\pi }{\mathrm{sin}^2\theta }\left(\frac{_0}{R_s}\right)^{1/2}\frac{\delta E_k}{\delta E_{B,s}}.$$
(4)
In the above, superscripts on the energies are dropped since $`\delta E_k^0/\delta E_{B,s}^0=(\delta M/\delta A_\varphi )(GM_H/A)`$ is an evolutionary invariant. Equation (4) shows that accretion is more efficient with increasing $`\mathrm{sin}\theta `$; outer-disk rings have magnetic field lines closer to the equator than inner-disk rings, providing greater moment arms for the magnetic torque.

Solution for toroidal field geometry — Under large magnetic hoop stresses, magnetic flux surfaces adjust their latitudes such that the toroidal magnetic field in the wind approaches a force-free configuration with $`B_\varphi R^1`$ (see e.g. the protostellar disk wind in Shu et al. (1995)). The magnetosphere is then effectively current-free except along the pole and the equator, with the poloidal pole current $`I_p`$ producing $`B_\varphi 2I_p/(cR)`$ elsewhere. Hence, $`_\mu A_\varphi =r^2B_r=2I_p[\mathrm{\Omega }\mathrm{sin}^2\theta ]^1`$ so that $`|\delta \tau _B|=2I_p\delta A_\varphi /c`$. Here, $`I_p`$ relates to the total normalized flux $`A𝑑\mu _\mu A_\varphi `$ by $`I_pA\mathrm{\Omega }(_{in})/(2|\mathrm{ln}(\theta _0/2)|)`$, where $`_{in}`$ is the innermost disk radius.

From equation (2), the TFG limit gives $`\mathrm{\Omega }\dot{}=(4I_p/c)(\delta A_\varphi /\delta M).`$ Using $`\mathrm{\Omega }()=\mathrm{\Omega }(_0)\varpi ^{3/2}`$ we find the finite-time singularity solution:

$`\varpi (t;A_\varphi )=(1t/t_f^{tfg})^2,`$ (5)
where

$$t_f^{tfg}=\frac{\delta J^0}{|\delta \tau _B^0|}=t_{ff}\frac{4_0}{\pi }\frac{\delta E_k}{\delta E_{B,s}}.$$
(6)
Here, $`_0(c/\sqrt{2})_0^1𝑑\theta (\mathrm{\Omega }\mathrm{sin}\theta )^1`$ is $`\left(_{in}^3/R_s_0^2\right)^{1/2}|\mathrm{ln}(\theta _0/2)|.`$ Going from $`_{in}`$ to the outside of the disk at $`_d`$, the radial factor in $`_0`$ decreases from $`(_{in}/R_s)^{1/2}`$ (which is order-unity) to $`(_{in}^3/R_s_d^2)^{1/2}`$ (which is of order $`_{in}/_d`$); the product $`t_{ff}_0`$ varies $`_0^{1/2}`$. Note that $`\delta E_B^0`$ in TFG is larger than $`\delta E_{B,s}^0`$ by a factor $`|_\mu A_\varphi |/A\mathrm{\Omega }(_{in})[\mathrm{\Omega }(_0)\mathrm{sin}^2\theta |\mathrm{ln}(\theta _0/2)|]^1`$.

For the inner disk, $`t_f^{tfg}<<t_f^{smg}`$ due to the geometrical factor $`4\theta _0^2|\mathrm{ln}(\theta _0/2)|<<1`$; the enhanced efficiency arises from squeezing of the poloidal field lines toward the pole by toroidal hoop stresses. For the outer disk, $`t_f^{tfg}:t_f^{smg}=4(_{in}/_d)^{3/2}|\mathrm{ln}(\theta _0/2)|`$, which is of order unity or less unless the effective beaming angle $`\theta _0`$ is extremely small. Thus, although inner-disk accretion is greatly enhanced when the magnetic wind becomes more stratified toward the poles, the overall lifetime set by outer disk accretion is not as sensitive to these geometric changes.

Dimensional estimates of accretion times — Dimensionally, the minimum inner-disk accretion time, from TFG, is

$$t_{in}=0.011\mathrm{s}g(\theta _0)\left(\frac{_{in}}{100\mathrm{km}}\right)^2\left(\frac{M_H}{10M_{}}\right)^1\frac{\delta E_k}{\delta E_{B,s}},$$
(7)
where $`g(\theta _0)=\left(1+\mathrm{ln}(\theta _0/1^{})/\mathrm{ln}(0.009)\right)`$ and $`\theta _0`$ is the angle of the innermost wind field line. Correspondingly, the maximum outer-disk accretion time is

$$t_d=0.057\mathrm{s}\left(\frac{_d}{1000\mathrm{km}}\right)^2\left(\frac{M_H}{10M_{}}\right)^1\frac{\delta E_k}{\delta E_{B,s}},$$
(8)
assuming $`_d>>_{in}`$ with SMG; otherwise, if $`_d_{in}`$, we would use the TFG result, which increases the time by a factor $`4|\mathrm{ln}(\theta _0/2)|`$ consistent with equation (7). These limits will bracket the interval over which disk accretion takes place.

## 3 Disk accretion and black hole spindown times compared

A ring spends the greatest portion of its lifetime near its initial radius; during the subsequent rapid infall phase, magnetic flux is approximately conserved. For fiducial estimates, we shall normalize to an initial kinetic-to-poloidal magnetic energy ratio $`100`$ for all rings, as found from Hawley (2000)’s numerical simulations of global, hot, MHD accretion disks. This energy ratio certainly varies in real systems; estimates based on simulations with different physics or initial conditions (e.g. heating from resistive dissipation, as in Stone & Pringle (2000); net poloidal flux, as in Hawley, Gammie, & Balbus (1996)) may decrease this ratio toward unity. The natural diversity in mean magnetizations may in part be responsible for the broad distributions of the two duration classes of GRBs.

Time-scale for short GRBs — Applying $`\delta E_k/\delta E_{B,s}=10100`$ in equation (7) or (8) (for a disk of size $`\stackrel{<}{}1000\mathrm{km}`$), the accretion time will be $`\stackrel{<}{}`$ a few seconds – comparable to that of the 2s event GRB 000310C (Jensen et al., 2001). In this scenario, short bursts represent hyperaccretion onto a slowly-spinning black hole.

Time-scale for long GRBs — What accounts for the long-duration bursts? If the black hole is initially rapidly spinning, then the burst may persist for the time $`t_H`$ required for angular momentum extraction by the Blandford-Znajek (1977) and related processes. Given a horizon flux $`2\pi A_H`$, the black hole torque for open fields is $`_H\mathrm{\Omega }_HA_H^2/c`$ (see Thorne et al. (1986)). To estimate $`A_H`$, assume that the black hole field strength is comparable to that from the inner part of the disk. In TFG, we find $`A_HA(2|\mathrm{ln}(\theta _0/2)|)^1`$ so that $`_H\mathrm{\Omega }_HA^2(4c|\mathrm{ln}(\theta _0/2)|^2)^1`$. For comparison, the total disk-wind angular momentum luminosity is equal to $`\tau _{}𝑑\tau _B`$; i.e. $`_d^{tfg}=\mathrm{\Omega }(_{in})A^2(c|\mathrm{ln}(\theta _0/2)|)^1`$. The spindown time $`t_H=2GM_H^2r_H\mathrm{\Omega }_Hc^2_H^1`$. Here, $`r_H=R_s\mathrm{cos}^2(\lambda /2)`$ is the radius of the black hole horizon; $`\mathrm{sin}\lambda a/M_H`$ is the ratio of specific angular momentum to the maximal Kerr value.

Taking $`\delta E_k/\delta E_{B,s}GM_HM_d/A^2`$, we obtain $`t_H=(8r_H/c)(\delta E_k/\delta E_{B,s})(M_H/M_d)|\mathrm{ln}(\theta _0/2)|^2.`$ Assuming $`aM`$ so $`r_HR_s/2`$, we find

$$t_H=88\mathrm{s}\left(\frac{M_H}{10M_{}}\right)\left(\frac{M_H/M_d}{100}\right)\left(\frac{\delta E_k/\delta E_{B,s}}{100}\right)g^2(\theta _0),$$
(9)
consistent with a bimodal offset of long- from short-duration bursts for $`M_d<<M_H`$. Note that $`t_H/t_{in}M_H/M_d`$, as magnetic torques on the disk and black hole are comparable, but $`J_H`$ exceeds $`J`$ of the inner disk by a factor of the mass ratio, assuming comparable specific angular momenta, as for a maximal-Kerr hole.

We remark that a black hole mass $`M_H`$ of about $`10M_{}`$, formed promptly in the hypernova scenario, is expected in view of the Kerr constraint $`J_HGM_H^2/c`$. For prompt collapse of a He-core of radius $`R_{He}`$, stripped of its hydrogen envelope and tidally locked with a binary companion of mass $`m`$ (Woosley, 1993; Paczyński, 1997; Iben & Tutukov, 1996) with an orbital separation $`\xi R_{He}`$,

$$M>M_HM\left(\frac{2}{5}\right)^3\left(\frac{c^2R_{He}}{GM\xi ^3}\right)^{3/2}\left(1+\frac{m}{M}\right)^{3/2}\left(\frac{\overline{\rho }}{\rho _c}\right)^2.$$
(10)
Here, the central density $`\rho _c`$ is that extrapolated from the He-mantle, with $`\overline{\rho }`$ denoting the mean density. For canonical values $`m=M=20M_{}`$, $`R_{He}=R_{}`$ and $`\xi =4`$, a black hole may form promptly provided the inequality on the left hand-side of equation (10) is satisfied; i.e. $`1>1.3\times 10^3\left(\overline{\rho }/\rho _c\right)^2`$. This would be true, if e.g. the He core is approximately fit by a polytrope with index $`n=3`$, for which the Lane-Emden relationship gives $`\rho _c50\overline{\rho }`$ (Kippenhahn & Weigert, 1990). Thus, rapidly rotating black holes formed in prompt collapse tend to be massive.

## 4 Suspended accretion and long GRBs

Long GRBs rely on the continuing presence of the torus. Hyperaccretion times (§2) are far shorter, however. We speculate that resolution of this paradox depends on the ability of the black hole to spin up the disk over interconnecting magnetic field-lines equivalent in poloidal topology to pulsar magnetospheres (Fig. 2 in van Putten (1999)). The black hole-torque on the torus is (adapted from Thorne et al. (1986))

$`\delta \tau _+{\displaystyle \frac{1}{c}}(\mathrm{\Omega }_H\mathrm{\Omega })\mathrm{sin}^2\theta (_\mu A_\varphi )\delta A_\varphi ,`$ (11)
for a flux-tube of field-lines between them (counting both above and below the midplane). The torus now has an inner face interacting with the black hole, and an outer face interacting with infinity. The primary role of the inner interaction is to extend the lifetime of the torus by preventing its accretion onto the black hole.

The total black hole torque on the torus, $`\tau _+`$, depends on the associated horizon flux $`2\pi A_H`$. Approach to the horizon tends to increase $`A_H`$; if $`2\pi A_H`$ becomes large compared to the open torus flux, an equilibrium state $`\tau _+\tau _{}`$ may be reached, and accretion onto the black hole stalls. This state is expected to be stable, since $`\tau _+`$ decreases with increasing $``$: if the torus gains (loses) angular momentum, it moves outward (inward) and reduces (increases) $`\tau _+`$. Such oscillations may give rise to intermittency. The black hole spindown proceeds on essentially the timescale in equation (9); the difference is that now the torus \- with its two faces - mediates the interaction.

More quantitatively, integration of equation (11) gives the net torque on the torus by the black hole as $`\tau _+(\mathrm{\Omega }_H\mathrm{\Omega })A^2f_H^2/c,`$ while the wind torque is now $`\tau _{}\mathrm{\Omega }A^2f_w^2[c|\mathrm{ln}(\theta _0/2)|]^1`$. Here, $`A`$ is now $`(2\pi )^1`$ times the total torus magnetic flux, and $`f_H`$ and $`f_w`$ are the fractions of $`A`$ passing through the inner and outer light surfaces, respectively, so that $`f_H+f_w1/21`$. The torus, “sandwiched” between the black hole and infinity, obeys an evolution equation

$$\dot{}\frac{2A^2}{M_dc}\left[f_H^2\left(\frac{\mathrm{\Omega }_H}{\mathrm{\Omega }}1\right)\frac{f_w^2}{|\mathrm{ln}(\theta _0/2)|}\right].$$
(12)
Accretion may therefore be halted – or reversed – if $`\mathrm{\Omega }_H\stackrel{>}{}\mathrm{\Omega }[1+(f_w/f_H)^2|\mathrm{ln}(\theta _0/2)|^1]`$. Early on, $`f_H<<1`$, and this equation will not be satisfied. Beginning near the midpoint of accretion when $`f_H\stackrel{>}{}f_w`$, and provided that $`\mathrm{\Omega }_H`$ is initiated close to its maximal value, accretion may be suspended for an interval $`t_H`$, until the value of $`\mathrm{\Omega }_H`$ drops below the critical value. Since in the “suspended” state, the torus gains and loses almost equal quantities of angular momentum, significant baryonic matter may be carried off in the wind.

## 5 Discussion and comparison with observations

We have revisited accretion timescales in magnetized black hole plus disk/torus systems, analyzing evolution when external torques rather than internal “turbulent” torques dominate. We propose two dynamical states – hyperaccretion and suspended accretion – for systems with low- or high-spin black holes. Around a slowly spinning black hole, wind torques drive the disk to a finite-time singularity – producing short bursts. Rapidly spinning black holes transfer sufficient angular momentum to the disk to arrest matter inflow until the black hole spins down – producing long bursts. A bimodal duration distribution occurs, provided that $`M_d<<M_H`$.

Our principal assumption is that external ordered torques dominate internal disordered ones; this requires significant poloidal magnetic flux. Determining how poloidal flux is created and when external torques prevail is a major unsolved problem. Numerical studies to date have shown the development of magnetic power spectra dominated by the largest scales permitted, in local disk simulations (e.g. Hawley, Gammie, & Balbus (1995)), and that magnetically-driven winds may develop from both cold and hot disks (e.g. Shibata & Uchida (1986); Stone & Norman (1994); Stone & Pringle (2000)), with dependence of the angular momentum loss rate on $`E_B`$ similar to analytic predictions (Kudoh, Matsumoto, & Shibata, 1998). Because the choice of numerical boundary conditions (particularly for $`B_\varphi `$) may affect the solution at the largest scale (see e.g. Ustyugova et al (1999)), very large dynamic range would be needed to assess the external magnetic torque.

Our model differs from expectations for a turbulence-dominated disk in several ways. First, a wind-dominated system converts gravitational energy into Poynting flux rather than thermalizing it. Such a “clean” system could have less radiative contamination/spectral degradation from a low-energy thermal component. Second, a magnetized wind is naturally collimated, unlike the fireball in the alternative scenario. Finally, only if significant poloidal flux is present can field geometry become unfavorable for matter inflow, allowing an extended disk lifetime. In turbulent disks, magnetic fields lie primarily parallel to the midplane, so flow onto the black hole proceeds even as magnetic stresses transfer spin energy and angular momentum outward (Krolik, 1999; Gammie, 1999).

Because most of the energy is liberated in the innermost regions, our hyperaccretion/short GRB and suspended-accretion/long GRB proposal implies similar intrinsic luminosities, but larger fluences in the second case. We thus expect short GRBs to feature afterglows similar to those of long GRBs, unless the environments of high- and low- angular momentum progenitors differ appreciably. This may be tested by the HETE-II mission, and is already supported by the afterglow detection to the 2s event GRB 000301C (Jensen et al., 2001).

The iron emission lines from GRB 970508 (Piro et al., 1999) may reflect the composition of progenitor matter. In the suspended accretion (long GRB) state, some torus matter is expected to be blown to infinity by the powerful black hole torque. We associate this baryonic wind with line-emitting regions for long burst systems; they are expected to be less powerful in short GRBs.

MVP acknowledges support from NASA Grant 5-7012 and an MIT C.E. Reed Fund. The authors thank the ITP/UCSB, where this work was initiated; NSF supports ITP under PHY94-07194. We are grateful to S. Kulkarni, J. Stone, and J. Hawley for useful discussions, and thank the referees for constructive comments.


format: text

text:
# First Measurement of the Photon Structure Function 𝑭_{𝟐,𝐜}^𝜸

## Introduction

For about 20 years measurements of photon structure functions give deep insight into the rich structure of a fundamental gauge boson, the photon. A recent review on this subject can be found in NIS-9904 . Here, the discussion is restricted to the measurement of $`F_{2,\mathrm{c}}^\gamma `$, which recently has been achieved for the first time. Only the main features of the analysis are given, the experimental details can be found in OPALPR294 .

The differential cross-section for deep inelastic electron-photon scattering, shown in Figure 1, is given by

$`{\displaystyle \frac{\mathrm{d}^2\sigma }{\mathrm{d}x\mathrm{d}Q^2}}`$ $`=`$ $`{\displaystyle \frac{2\pi \alpha ^2}{xQ^4}}\left[\left(1+(1y)^2\right)F_2^\gamma (x,Q^2)y^2F_\mathrm{L}^\gamma (x,Q^2)\right].`$ (1)
Here $`Q^2`$ is the absolute value of the four momentum squared of the exchanged virtual photon, $`\gamma ^{}`$, $`x`$ and $`y`$ are the usual dimensionless variables of deep inelastic scattering and $`\alpha `$ is the fine structure constant. In experimental analyses $`y^2`$ is usually small. Consequently, the term proportional to the longitudinal structure function $`F_\mathrm{L}^\gamma `$ can be neglected and the differential cross-section is directly proportional to $`F_2^\gamma `$, which is related to the sum over the quark parton distribution functions $`q^\gamma `$ of the quasi-real photon, $`\gamma `$, via

$`F_2^\gamma (x,Q^2)`$ $`=`$ $`x{\displaystyle \underset{q=u,d,s}{\overset{c,b,t}{}}}\mathrm{e}_\mathrm{q}^2\left[q^\gamma (x,Q^2)+\overline{q}^\gamma (x,Q^2)\right].`$ (2)
Due to the large scale established by their masses, the contribution to $`F_2^\gamma `$ from heavy quarks can be calculated in perturbative QCD. At present collider energies only the contribution of charm quarks $`F_{2,\mathrm{c}}^\gamma `$ is important. Like the structure function for light quarks, $`F_{2,\mathrm{c}}^\gamma `$ receives contributions from the point-like and the hadron-like component of the photon shown in Figure 1.

Because of the charge of the charm quarks their contribution to $`F_2^\gamma `$ is large and the importance increases for increasing values of $`Q^2`$, as can be seen from Figure 2, which shows the contributions from light quarks and from charm quarks separately, as predicted by the GRV parametrisations GRV .

Charm quarks can only be produced if the photon-photon invariant mass $`W`$ is at least twice the mass of the charm quarks $`m_\mathrm{c}`$. Using $`x=Q^2/(Q^2+W^2)`$ this leads to the varying production threshold in $`x`$ as a function of $`Q^2`$ seen in Figure 2.

Close to the production threshold, the point-like contribution to $`F_{2,\mathrm{c}}^\gamma `$ is accurately approximated by the prediction of the lowest order Bethe-Heitler formula. For quasi-real photons also the next-to-leading order (NLO) predictions have been calculated in LAE-9401 .

For the hadron-like contribution the photon-quark coupling must be replaced by the gluon-quark coupling, and the Bethe-Heitler formula has to be integrated over the allowed range in fractional momentum of the gluon using a parametrisation of the gluon distribution function of the photon, see e.g. NIS-9904 .

The predicted behaviour of the point-like and hadron-like component of $`F_{2,\mathrm{c}}^\gamma `$ for different values of $`m_\mathrm{c}`$ is shown in Figure 3, using the SaS1D SAS  and GRS GLU-9501  parametrisations. For $`x>0.1`$ the structure function is saturated by the point-like component which is only slowly suppressed for increasing virtualities $`P^2`$ of the quasi-real photon. In contrast, the hadron-like contribution dominates at small values of $`x`$ and decreases much faster for increasing $`P^2`$. Finally, lowering the mass of the charm quarks leads to a higher threshold in $`x`$.

Given this predicted behaviour, the region of $`x>0.1`$ can be used to test a purely perturbative NLO QCD prediction with only $`m_\mathrm{c}`$ and $`\alpha _s`$ as free parameters, and the low $`x`$ behaviour mainly probes the gluon distribution function of the photon.

## Monte Carlo Models

The LO Monte Carlo generators HERWIG 5.9 MAR-9201  and Vermaseren Vermas  are used, both with $`m_\mathrm{c}=1.5`$ $`\mathrm{GeV}`$. In HERWIG charm production is modelled using matrix elements for massless charm quarks, together with the GRV parametrisation for the parton distributions of the photon, again for massless charm quarks. The effect of the charm quark mass is only accounted for by not simulating events with $`W<2m_\mathrm{c}`$. Due to the massless approach used in HERWIG and the crude treatment at threshold, the predicted charm production cross-section is likely to be too large. The Vermaseren generator is based on the Quark Parton Model (QPM) and consequently does not take into account the hadron-like component of the photon structure. However, the complete dependence of the cross-section on the different photon helicities is modelled.

## The measurement of $`𝑭_{\mathrm{𝟐}\mathbf{,}𝐜}^𝜸`$

The measurement of $`F_{2,\mathrm{c}}^\gamma `$ proceeds along the same lines as the measurement of $`F_2^\gamma `$ with the addition of the identification of the charm quarks via the reconstruction of $`\mathrm{D}^{}`$ mesons.

Events are selected with an energy of the scattered electron above 50 $`\mathrm{GeV}`$, measured in the angular ranges (a) $`3355`$ mrad or (b) $`60120`$ mrad from either beam direction, thereby covering the approximate range in $`Q^2`$ of $`5100`$ $`\mathrm{GeV}^2`$. The visible hadronic mass $`W_{\mathrm{vis}}`$ is required to be below 60 $`\mathrm{GeV}`$. Charm quarks are identified via $`\mathrm{D}^{}\mathrm{D}^0\pi `$, followed by $`\mathrm{D}^0K\pi `$ or $`\mathrm{D}^0K\pi \pi \pi `$. Using $`f(\mathrm{c}D^{})=0.235\pm 0.011`$ and the branching ratios of the $`\mathrm{D}^0`$ decay modes of $`0.02630\pm 0.00082`$ and $`0.0519\pm 0.0029`$, this analysis covers only about 4$`\%`$ of all events containing a pair of charm quarks. For a clear acceptance the $`\mathrm{D}^{}`$ mesons are further required to fulfill, $`|\eta ^\mathrm{D}^{}|<1.5`$ and $`p_\mathrm{T}^\mathrm{D}^{}>1\text{ or }3`$ $`\mathrm{GeV}`$ for (a) or (b). Together with a typical selection efficiency of about 25$`\%`$ only about 1$`\%`$ of all $`\mathrm{c}\overline{\mathrm{c}}`$ events are positively identified.

Figure 4 shows the distribution of the difference between the $`\mathrm{D}^{}`$ and the $`\mathrm{D}^0`$ candidate mass. In both samples a clear peak is visible around $`\mathrm{\Delta }M=145.4`$ $`\mathrm{MeV}`$. Subtracting the background, obtained from a fit to the upper sideband of the signal, $`29.8\pm 5.9(\mathrm{stat})`$ $`\mathrm{D}^{}`$ mesons are found in the peak region.

Figure 5 shows the distributions of $`W_{\mathrm{vis}}`$ and of the measured $`Q^2`$ in comparison to the predictions of the HERWIG and Vermaseren Monte Carlo generators normalised to the number of data events. Both Monte Carlo generators give a good description of the shape of the data distributions.

The cross-section for $`\mathrm{D}^{}`$ production is determined in the well-measured kinematic range described above. Based on this and the extrapolation factors obtained from the Monte Carlo models the full cross-section $`\sigma (\mathrm{e}^+\mathrm{e}^{}\mathrm{e}^+\mathrm{e}^{}\mathrm{c}\overline{\mathrm{c}})`$ and $`F_{2,\mathrm{c}}^\gamma `$ are evaluated in two bins of $`x`$ with $`0.0014<x<0.1`$ and $`0.1<x<0.87`$.

For $`x>0.1`$ the predictions of the Vermaseren and HERWIG Monte Carlo models are very similar. In contrast, for $`x<0.1`$, there are two main differences. Firstly the selection efficiency for events with $`\mathrm{D}^{}`$ mesons fulfilling the kinematical requirements is different, and secondly, and even more important, the predicted cross-section within the invisible phase-space is largely different for the two models, resulting in different extrapolation factors, 12.9/5.1 for HERWIG/Vermaseren.

Since the hadron-like contribution is neglected in the QPM, the Vermaseren cross-section is much smaller than the LO and the NLO cross-section for $`x<0.1`$. In contrast, mainly due to the massless approach taken, the prediction from HERWIG is higher than the cross-section from the LO and the NLO calculation. Therefore it is likely that the correct cross-section, and therefore the correct extrapolation factor, lies within the range of the two Monte Carlo predictions.

The measured $`F_{2,\mathrm{c}}^\gamma `$ for $`Q^2=20`$ $`\mathrm{GeV}^2`$ is shown in Figure 6. The central values are obtained by averaging the results using the HERWIG and Vermaseren Monte Carlo models, and half the difference is taken as extrapolation error, which dominates the uncertainty for $`x<0.1`$. The NLO prediction is based on $`m_\mathrm{c}=1.5`$ $`\mathrm{GeV}`$, the renormalisation and factorisation scales are chosen to be $`\mu _\mathrm{R}=\mu _\mathrm{F}=Q`$, and the hadron-like contribution to $`F_{2,\mathrm{c}}^\gamma `$ uses the GRV parametrisation. The NLO corrections are small for the whole $`x`$ range. The band for the NLO calculation is evaluated by varying $`m_\mathrm{c}`$ between 1.3 and 1.7 GeV and using $`Q/2\mu _\mathrm{R}=\mu _\mathrm{F}2Q`$.

For $`x>0.1`$ the error of the measured cross-section is dominated by the statistical uncertainty, and the NLO calculation with only $`m_\mathrm{c}`$ and $`\alpha _s`$ as free parameters is in good agreement with the data. In contrast, for $`x<0.1`$, the result suffers from the strong model dependence discussed above. Despite this uncertainty the corrected data suggest a cross-section which is above the purely point-like component, i.e. the hadron-like component of $`F_{2,\mathrm{c}}^\gamma `$ is non-zero.

### Conclusion and Outlook

In conclusion, for $`x>0.1`$, the purely perturbative NLO calculation is in good agreement with the measurement and for $`x<0.1`$, the measurement suggests a non-zero hadron-like component of $`F_{2,\mathrm{c}}^\gamma `$.

By using the massive matrix elements available in HERWIG6.1 and the full integrated luminosity of more than 500 $`\mathrm{pb}^1`$ of the LEP2 programme, the measurement is likely to be improved considerably, both concerning the statistical and the systematic error.
Acknowledgement:
I wish to thank the organisers of this interesting conference, and especially Alex Finch. They created a fruitful atmosphere throughout the meeting and made attending the meeting a very nice experience.


text:
# Opportunity Cost Algorithms for Combinatorial Auctions

## 1 Introduction

Auctions are arguably the simplest and most popular means of price determination for multilateral trading without intermediary market makers . This paper considers the setting where there are (1) a group of competing bidders who bid to possess the auction objects and (2) an auctioneer who determines which bidders win which objects.

For the case of allocating a single object to one of many bidders, there is a wealth of literature on the following four widely used forms of auction . In an *English auction* or *ascending bid auction*, the price of an object is successively raised until only one bidder remains and wins the object. In a *Dutch auction*, which is the converse of an English auction, an initial high price is subsequently lowered until a bidder accepts the current price. In a *first-price sealed-bid auction*, potential buyers submit sealed bids for an object. The highest bidder is awarded the object and pays the amount of her bid. In a *second-price sealed-bid auction*, the highest bidder wins the object but pays a price equal to the second-highest bid. In all these forms of auction, the auctioneer can determine the winning bid in time linear in the number of bids in a straightforward manner.

For the case of allocating multiple objects to multiple bidders, combinatorial auctions are perhaps the most important form of auctions in the Internet Age, where bidders are increasingly software agents. Oftentimes a bid by an agent is a subset of the auction objects, and the agent needs the entire subset to complete a task. Different bids may share the same object, but the winning bids must not share any object . Combinatorial auctions were first proposed by Rassenti et al.  as one-round mechanisms for airport time slot allocation. Banks et al. , DeMartini et al. , and Parkes and Ungar  formulated multiple-round mechanisms. It is in general $`NP`$-hard for the auctioneer to determine a set of winning bids of a combinatorial auction which maximizes the revenue of the auction. To address this computational difficulty, Rothkopf et al.  placed constraints on permissible bids. Lehmann et al.  and Fujishima et al.  considered approximation algorithms. Sandholm and Suri  designed *anytime* algorithms, which return a sequence of monotonically improving solutions that eventually converges to optimal.

In this paper, we propose a general framework to exploit topological structures of the bids to determine the winning bids with a provably good approximation ratio in linear time. The following discussion uses the sale of a car as a light-hearted example to explain our computational problems and key concepts.

Imagine that we are in the business of auctioning used cars. If we insist on selling each car as a unit, we can sell each car to the highest bidder. If we are willing to sell parts of the car, we can still sell each part to the highest bidder. But suppose that some bidders are only interested in buying several parts at once: Alice may not want to buy a tire unless she can get the wheel that goes with it, while Bob might only be interested in both rear wheels and the axle between them. How do we decide which of a set of conflicting bids to accept?

We will assume that our only goal is to maximize our total revenue. Then we can express this problem as a simple combinatorial optimization problem. We have some universe $`𝒪`$ of objects, and our buyers supply us with a set $`𝒜`$ of bids. The $`i`$-th bid consists of a subset $`A_i`$ of $`𝒪`$ and a price $`p_i`$ that the buyer is willing to pay for all of the objects in $`S_i`$. We would like to choose a collection of bids $`𝒜`$ that yields the best possible total price while being *consistent*, in the sense that no two sets $`A_i`$ and $`A_j`$ in $``$ overlap.

As the auctioneer, we can construct a *bid graph* $`G`$ whose nodes are the bids and which has an edge between any two bids that share an object. Then, a set of consistent bids is simply an independent set in $`G`$, i.e., a set of nodes no two of which are connected by an edge. Each node is given a weight equal to the value of the bid it represents.

Sadly, this means that the problem of finding the most valuable consistent set of bids is a thinly-disguised version of the maximum weight independent set problem, which is not only $`NP`$-hard, but cannot be approximated to within a ratio $`O(n^{1ϵ})`$ for an $`n`$-node graph unless $`P=NP`$ .111 The fact that the bid graph is defined by the intersections of a collection of sets does not by itself help; any graph can be defined in this way. Even for the simplest case when all node weights are one, the maximum weight independent set problem is $`NP`$-hard even when every vertex has degree at most $`d`$ for any $`d3`$, and in fact cannot be approximated within a ratio of $`d^\epsilon `$ for some $`\epsilon >0`$ unless $`P=NP`$ . The best known algorithm (for arbitrary $`d`$) achieves an approximation within a factor of $`O(d/\mathrm{log}\mathrm{log}d)`$ . As a result, it seems hopeless if we model our combinatorial auction problem as an independent set problem unless we exploit the topological structure of the underlying bid graph.

Using ideas from the interval selection algorithm of Berman and DasGupta , we describe in Section 2 a linear-time improvement of the greedy algorithm, called the *opportunity cost algorithm*, for approximating maximum weight independent sets in ordered graphs.222These are graphs in which the nodes have been assigned an order; as we will see in Section 3.5, the choice of order for a given bid graph can have a large effect on how good an approximation we can get. We then describe a similar algorithm called the *local ratio opportunity cost algorithm*, based on ideas from the resource allocation algorithms of Bar-Noy et al.. Both algorithms produce the same output, but the first has a more iterative structure and is easier to implement while the second has a more recursive structure and is easier to analyze.

These opportunity cost algorithms distinguish themselves from the straightforward greedy algorithm by taking into account the cost of excluding previously considered neighbors of a chosen node. Since this accounting requires propagating information only between neighbors, it increases the running time by at most a small constant factor, and yet in many cases produces a great improvement in the approximation ratio. The quality of the approximation depends on the local structure of the ordered input graph $`G`$. For each node $`v`$ in $`G`$, we examine all of its successors (adjacent nodes that appear later in the ordering). The maximum size of any independent set among $`v`$ and its successors is called the *directed local independence number at $`v`$*; we will write it as $`\beta (v)`$. The maximum value of $`\beta (v)`$ over all nodes in the graph will be written as $`\beta (G)`$,333Or simply $`\beta `$ when $`G`$ is clear from the context. and is the directed local independence number of $`G`$. Our algorithms approximate a maximum weight independent set to within a factor of $`\beta `$. By comparison, the greedy algorithm approximates a maximum weight independent set within a ratio of the maximum size of any independent subset of both the predecessors and the successors of any node, which in general can be much larger than $`\beta `$ (see Section 2).

These new approximation results are useful only if we can exhibit interesting classes of graphs for which $`\beta `$ is small. Graphs with $`\beta =1`$ have been extensively studied in the graph theory literature; these are known as *chordal graphs*, and are precisely those graphs that can be represented as intersection graphs of subtrees of a forest, a class that includes both trees and interval graphs (more details are given in Section 3.1). We give additional results showing how to compute upper bounds on $`\beta `$ for more general classes of graphs in Sections 3.2 and 3.3.

Among these tools for bounding $`\beta `$, one of particular interest to our hypothetical combinatorial auctioneer is the following generalization of the fact that intersection graphs of subtrees have $`\beta `$ equal to one. Suppose that we have an *object graph* whose nodes are objects and in which an edge exists between any two objects that are relevant to each other in some way. (In the car example, there might be an edge between a wheel and its axle but not between a wheel and the hood ornament.) We demand that the objects in each bid be *germane* in the sense that they must form a connected node subset of the object graph. For many sparse object graphs, the intersection graph of all connected sets of vertices can be ordered so that a later set intersects an earlier set only if it intersects a “frontier set” that may be much smaller than the earlier set. It is immediate that $`\beta `$ for the intersection graph is bounded by the size of the largest frontier set (more details are given in Lemma 8). Examples of such graphs are those of low treewidth (Theorem 9) and planar graphs (Corollary 10).

In Section 4 we show how to handle more complex constraints on acceptable sets of bids. We investigate scenarios where bids are grouped by bidder, and that each bidder is limited to some maximum number of winning bids (an *unweighted budget constraint*), or some maximum total cost of winning bids (a *weighted budget constraint*). By charging later bids an approximate opportunity cost for earlier bids in the same budget groups, we can solve these problems approximately with ratio $`\beta +1`$ with unweighted constraints and $`2\beta +3`$ for weighted constraints. The results for unweighted budget constraints can be further generalized for more complicated constraints.

Finally, in Section 5 we discuss some open problems suggested by the current work.

## 2 Simple combinatorial auctions

In this section, we describe our algorithms for approximating the maximum weight independent set problem, the opportunity cost algorithm and the local ratio opportunity cost algorithm . Both algorithms return the same approximation.

### 2.1 The opportunity cost algorithm

We will write $`uv`$ if $`uvE`$ and call $`u`$ a *predecessor* of $`v`$ and $`v`$ a *successor* of $`u`$. The set of all predecessors of $`u`$ will be written as $`\delta ^{}(u)`$ and the set of all successors as $`\delta ^+(u)`$.

Given a directed acyclic graph $`G_0=(V_0,E_0)`$ with weights $`weight(v)`$ for each $`v`$ in $`V`$, the opportunity cost algorithm, Opcost, proceeds in two stages:

1. Traversing the nodes according to the topological order of $`G_0`$, compute a *value* $`value(u)`$ for each node $`u`$. This value represents an estimate of the gain we expect by including $`u`$ in the independent set; it is computed by taking the weight of $`u`$ and subtracting off an *opportunity cost* consisting of the values of earlier positive-value nodes that conflict with $`u`$. Formally, let

$$value(u)=weight(u)\underset{vu}{}\mathrm{max}(0,value(v)).$$
(1)
2. Processing the nodes in reverse topological order, add any node with non-negative value to the desired independent set $``$ and discard its predecessors. Formally, let

$$select(u)=[value(u)0]v\delta ^+(u):\neg select(v).$$
(2)

The output of the algorithm is the set $``$ defined as all $`u`$ for which $`select(u)`$ is true. This set $``$ is clearly independent. In Section 2.3, we examine how close $``$ is to optimal.

### 2.2 The local ratio opportunity cost algorithm

The *local ratio technique* can be used to recursively find approximate solutions to optimization problems over vectors in $`^n`$, subject to a set of feasibility constraints. It was originally developed by Bar-Yehuda and Even , and later extended by Bafna et al. , Bar-Yehuda , and Bar-Noy et al. .

Let $`w^n`$ be a *weight* vector. Let $`F`$ be a set of feasibility constraints. A vector $`x^n`$ is a *feasible solution* to a given problem $`(F,w)`$ if it satisfies all the constraints in $`F`$. The *$`w`$-weight* of a feasible solution $`x`$ is defined to be the dot-product $`wx`$; for $`r1`$, $`x`$ is an *$`r`$-approximation* with respect to $`(F,w)`$ if $`rwxwx^{}`$, where $`x^{}`$ is a feasible solution maximizing the $`w`$-weight. An algorithm is said to have an *approximation ratio* of $`r`$ if it always returns an $`r`$-approximate solution.

###### Lemma 1 (Local Ratio Lemma )

Let $`F`$ be a set of feasibility constraints. Let $`w`$, $`w_1`$ and $`w_2`$ be weight vectors such that $`w=w_1+w_2`$. If $`x`$ is an $`r`$-approximation with respect to $`(F,w_1)`$ and $`(F,w_2)`$, then $`x`$ is an $`r`$-approximation with respect to $`(F,w)`$.

We now describe the local ratio opportunity cost algorithm, LR-Opcost. Given a directed acyclic graph $`G_0=(V_0,E_0)`$ with weights $`weight(v)`$ for each $`vV_0`$, we pass $`(G_0,weight())`$ to the following recursive procedure. This procedure takes as input a graph $`G`$ and a weight function $`w`$ and proceeds as follows:

1. Delete all nodes in $`G`$ with non-positive weight. Let this new graph be $`G_2`$.
2. If $`G_2`$ has no nodes, return the empty set.
3. Otherwise, select a node $`u`$ with no predecessors in $`G_2`$, and decompose the weight function $`w`$ as $`w=w_1+w_2`$, where

$$w_1(v)=\{\begin{array}{cc}w(u)\hfill & \text{if }v\{u\}\delta ^+(u)\text{,}\hfill \\ 0\hfill & \text{otherwise,}\hfill \end{array}$$

and $`w_2=ww_1`$.
4. Solve the problem recursively using $`(G_2,w_2)`$ as input. Let $`_2`$ be the approximation to a maximum weight independent set returned by this recursive call.
5. If $`_2\{u\}`$ is an independent set, return $`=_2\{u\}`$. Otherwise, return $`=_2`$.

###### Theorem 2

Opcost and LR-Opcost return the same approximation to a maximum weight independent set.

Proof:  Consider a recursive call $`C`$ of LR-Opcost. Let $`u`$ be the node that is selected to be processed in step LR3. All of $`u`$’s predecessors in the original graph $`G_0`$ have either been processed in a previous step LR3 or deleted in some step LR1. Therefore, the current weight of $`u`$, $`w(u)`$, as seen by the recursive call $`C`$, is just $`value(u)`$, as defined in step OC1 of Opcost. Furthermore, we add node $`u`$ to our independent set in step OC2 if and only if we add $`u`$ to our independent set in step LR5.

### 2.3 Approximation ratios

###### Theorem 3

Opcost and LR-Opcost return a $`\beta (G)`$-approximation to a maximum weight independent set. Furthermore, there exist weights for which this bound is tight.

Proof:  We will prove the result for LR-Opcost. The full result follows from Theorem 2. Clearly, the returned set of nodes $``$ is an independent set. By Lemma 1, we need only show that $``$ is a $`\beta `$-approximation with respect to $`w_1`$ and $`w_2`$. We will prove this by induction on the recursion. The base case of the recursion is trivial, since there are no positive weight nodes.

For the inductive step, assume that $`_2`$ is a $`\beta `$-approximation with respect to $`w_2`$. Then $``$ is also a $`\beta `$-approximation with respect to $`w_2`$ since $`w_2(u)=0`$ and $`_2\{u\}`$.

To show that $``$ is a $`\beta `$-approximation with respect to $`w_1`$, we will derive an upper bound $`\beta w(u)`$ on the maximum $`w_1`$-weight independent set and a lower bound $`w(u)`$ on the $`w_1`$-weight of any *$`u`$-maximal* independent set of nodes. A $`u`$-maximal independent set of nodes either contains $`u`$ or adding $`u`$ to it violates the property that it is an independent set. Our $`w_1`$ performance bound is $`\beta w(u)/w(u)=\beta `$. Note that only $`u`$ and its successor nodes will have a nonzero contribution to $`w_1`$-weight.

The total weight of a maximum $`w_1`$-weight independent set is at most $`\beta (u)w(u)\beta (G)w(u)=\beta w(u)`$. The total weight of any $`u`$-maximal independent set is at least $`w(u)`$, since any such set contains at least one element of $`u\delta ^+(u)`$, and all such nodes are assigned weight $`w(u)`$. Since the algorithm always chooses a $`u`$-maximal set, its $`w_1`$ performance bound is $`\beta `$.

To show the bound is tight, pick some $`v`$ that maximizes $`\beta (v)`$, and assign it weight $`1`$ and all of its successors weight $`1ϵ`$, where $`ϵ>0`$. Let every other node in $`G`$ have weight $`0`$. When we run Opcost, the value of $`v`$ will be $`1`$, the value of each of its successors will be $`ϵ`$, and the value of any other node is irrelevant because it has zero weight. Thus Opcost returns a set of total weight $`1`$ but the maximum weight independent set has total weight at least $`\beta (u)(1ϵ)`$.

### 2.4 Running time

###### Theorem 4

The running times of both Opcost and LR-Opcost are linear in the size of the input graph $`G_0`$.

Proof:  Opcost computes $`value(v)`$ for each node $`v`$ in time proportional to its indegree, and computes $`select(v)`$ for each node in time proportional to its outdegree, for a total time of $`O(|V_0|+|E_0|)`$. In the case of LR-Opcost, a recursive call is made at most once for each node in the graph, and defining $`w_1`$ and $`w_2`$ in each call takes time proportional to the node’s outdegree, for a total running time of $`O(|V_0|+|E_0|)`$.

## 3 Properties of $`\beta `$

For any $`v`$, $`\beta (v)`$ is at most the larger of $`1`$ or the outdegree of $`v`$. Thus, $`\beta (G)`$ is at most the larger of $`1`$ or the maximum degree of $`G`$. In many cases we can use the structure of $`G`$ to get a much better bound.

### 3.1 Graphs with $`\beta =1`$

Graphs with orientations for which $`\beta =1`$ can be characterized completely. These are the *chordal* graphs, also known as *triangulated* graphs or *rigid circuit* graphs. The defining property of a chordal graph is that no cycle of length $`4`$ or more appears as an induced subgraph. A succinct discussion of these graphs, including a variety of characterizations as well as several examples of interesting families of chordal graphs, can be found in \[14, pp. 280–281\]. For our purposes the most useful of these characterizations are stated in the following lemma:

###### Lemma 5

Let $`G`$ be an undirected graph. Then the following properties of $`G`$ are equivalent:

1. $`G`$ is chordal.
2. $`G`$ is the intersection graph of subtrees of a forest.
3. $`G`$ has an ordering $`G^{}`$ for which the successors of any node form a clique. Such an ordering is called a *perfect elimination ordering*. Restated in terms of $`\beta `$, $`G`$ has an ordering $`G^{}`$ for which $`\beta (G^{})=1`$.

Proof:  See \[14, pp. 280-281\].

Chordal graphs can be recognized and ordered using a specialized version of breadth-first search in $`O(|V|+|E|)`$ time as shown by Rose et al. , and their maximum cardinality independent sets can be computed in $`O(|V|+|E|)`$ time as shown by Gavril . Gavril’s algorithm is essentially the same as step OC1 of the opportunity cost algorithm; it chooses all nodes with positive value and works because the sets $`\{v:uv\}`$ for each $`u`$ in the independent set form a clique covering. However, this algorithm does not deal with weights.

Special cases of graphs with $`\beta =1`$ include trees, interval graphs, and disjoint unions of cliques. The last are particularly nice:

###### Lemma 6

Let $`G`$ be a disjoint union of cliques. Then *every* orientation $`G^{}`$ of $`G`$ has $`\beta (G^{})=1`$.

Proof:  For each $`u`$ in $`G^{}`$, $`\delta ^+(u)`$ is a clique.

### 3.2 Graphs with larger $`\beta `$ values

For general graphs, we cannot compute $`\beta `$ even approximately. However, we can bound the $`\beta `$ values of many graphs using the tools in this section.

###### Lemma 7

Let $`G`$ be a directed graph.

1. If $`G=G_1G_2`$, then $`\beta (G)\beta (G_1)+\beta (G_2)`$.
2. If $`G`$ is a node-induced subgraph of $`H`$, then $`\beta (G)\beta (H)`$.

Proof:  Let $`u`$ be a node of $`G`$. Let $`\delta ^+(u)`$, $`\delta _1^+(u)`$, $`\delta _2^+(u)`$, and $`\delta _H^+(u)`$ be the set of all successors of $`u`$ in $`G`$, $`G_1`$, and $`G_2`$, respectively. Let $`A`$ be any independent subset of $`\delta ^+(u)`$. Then

1. $`|A||A\delta _1^+(u)|+|A\delta _2^+(u)|\beta (G_1)+\beta (G_2)`$, and
2. $`A`$ is an independent subset of $`\delta _H^+(u)`$, implying $`|A|\beta (H)`$.

###### Lemma 8

Let $`G`$ be the intersection graph of a set system $`𝒜`$ whose union is $`𝒪`$. Let $`G`$ be ordered by an ordering $`<`$ such that for each $`A𝒜`$ there exists a “frontier set” $`S_AU`$ of size at most $`k`$, so that if $`A<B`$ and $`AB\mathrm{}`$, then $`S_AB\mathrm{}`$. Then $`\beta (G)k`$. (Note that $`S_A`$ need not be contained in $`A`$.)

Proof:  Let $`B_1,\mathrm{},B_l`$ be some independent set of successors of $`A`$. Under the conditions of the lemma each $`B_i`$ intersects $`S_A`$. But since the $`B_i`$ do not themselves intersect, each must intersect $`S_A`$ in a distinct element. Thus there are at most $`k`$ of them.

The converse of the lemma does not hold. Instead, its proof shows that the *clique covering number* $`\overline{\chi }`$ of $`\delta ^+(A)`$ (defined as the minimum size of any set of cliques whose union is $`\delta ^+(A)`$) is at most $`k`$, since the set of all $`B`$ that intersect $`S_A`$ at any particular element form a clique. Note that *any* directed acyclic graph in which $`\overline{\chi }(\delta ^+(v))`$ is bounded can be represented as an intersection graph with small frontier sets as in Lemma 8,444The trick is to add a new common element to all members of each clique, and let $`S_A`$ be the set of all such new elements for the cliques that cover $`\delta ^+(A)`$. in general the independence number of $`\delta ^+(v)`$ may be smaller than the clique covering number.

When $`𝒜`$ consists of connected node subsets of some graph $`H`$, we can obtain good orderings of the intersection graph $`G`$ of $`𝒜`$ by exploiting the structure of $`H`$.

We start by reviewing the definition of treewidth. A *tree decomposition* of an *undirected* graph $`H=(V,E)`$ consists of a tree $`T`$ and a family of sets $`𝒱=\{V_t\}`$ where $`t`$ ranges over nodes of $`T`$, satisfying the following three properties:

1. $`_{tT}V_t=V`$.
2. For every edge $`uv`$ in $`E`$, there is some $`V_t`$ that contains both $`u`$ and $`v`$.
3. If $`t_2`$ lies on the unique path from $`t_1`$ to $`t_3`$ in $`T`$, then $`V_{t_1}V_{t_3}V_{t_2}`$.

The *width* of a tree decomposition $`(T,𝒱)`$ is $`\mathrm{max}|V_t|1`$. The *treewidth* $`tw(H)`$ of a graph $`H`$ is the smallest width of any tree decomposition of $`H`$.

###### Theorem 9

If $`G`$ is an intersection graph of connected node subsets $`𝒜`$ of some graph $`H`$ with treewidth $`k`$, then there is an orientation $`G^{}`$ of $`G`$ with $`\beta (G^{})k+1`$. Given $`𝒜=\{A_i\}`$ and a tree decomposition $`(T,𝒱=\{V_t\})`$ of $`H`$, this orientation can be computed in time $`O(_i|A_i|+|T|+_t|V_t|)`$, which is linear in the size of the input.

Proof:  Let $`(T,𝒱)`$ be a tree decomposition of $`H`$ with width $`k`$. We will use this tree decomposition to construct an ordering of the connected node subsets of $`H`$, with the property that if $`A<B`$ then either $`AB=\mathrm{}`$ or $`B`$ intersects some frontier set $`S_A`$ with at most $`k+1`$ elements. The full result then follows from Lemma 8.

Choose an arbitrary root $`r`$ for $`T`$, and let $`t_1t_2`$ if $`t_1`$ is an ancestor of $`t_2`$ in the resulting rooted tree. Extend the resulting partial order to an arbitrary linear order. For each connected node subset $`A`$ of $`H`$, let $`t_A`$ be the greatest node in $`T`$ for which $`V_{t_A}`$ intersects $`A`$. Given two connected node subsets $`A`$ and $`B`$ of $`H`$, let $`A<B`$ if $`t_A<t_B`$ and extend the resulting partial order to any linear order.

Ordering $`T`$ can be done in $`O(|T|)`$ time using depth first search. We can then compute and the maximum node in $`T`$ containing each node of $`H`$ in time $`O(_tV_t)`$ by considering each $`V_t`$ in order. The final step of ordering the $`A_i`$ in the given set system $`𝒮`$ takes $`O(_i|A_i|)`$ time, since we must examine each element of each $`A_i`$ to find the maximum one. The total running time is thus linear in the size of the input.

Now suppose $`AB`$ in this ordering. We will show that any such $`B`$ intersects $`V_{t_A}`$, and thus that $`V_{t_A}`$ is our desired frontier set $`S_A`$. There are two cases.

If $`t_A=t_B`$, we are done.

The case $`t_A<t_B`$ is more complicated. We will make heavy use of a lemma from , which concern the effect of removing some node $`t`$ from $`T`$. Their Lemma 2.3 implies that if $`x,x^{}`$ are not in $`V_t`$, then either $`x`$ and $`x^{}`$ are separated in $`H`$ by $`V_t`$ or $`x`$ and $`x^{}`$ are in the same branch (connected component) of $`Tt`$.

Let $`p`$ be the parent of $`t_A`$ (which exists because $`t_A`$ is not the greatest element in the tree ordering). We have $`AV_p=\mathrm{}`$ since $`p>t_A`$. Since $`A`$ is a connected set, it cannot be separated without removing any of its nodes; thus by Lemma 2.3 every element of $`A`$ is in the same branch of $`Tp`$, which consists precisely of the subtree of $`T`$ rooted at $`t_A`$.

Now $`B`$ contains at least one node $`x`$ in the vertex set of an element of the subtree rooted at $`t_A`$, and at least one node $`x^{}`$ in $`V_{t_B}`$, which is not in this subtree because $`t_B>t_A`$. So by Lemma 2.3 of , either one of $`x,x^{}`$ is in $`V_{t_A}`$ or $`B`$ is separated by $`V_{t_A}`$. In the latter case $`B`$ intersects $`V_{t_A}`$ since $`B`$ is also connected.

Applying Theorem 9 to planar graphs gives:

###### Corollary 10

If $`G`$ is the intersection graph of a family $`𝒜`$ of connected node subsets of a planar graph $`H`$ with $`n`$ nodes, then there is an orientation $`G^{}`$ of $`G`$ with $`\beta (G^{})=O(\sqrt{n})`$. Given $`H`$, a data structure of size $`O(n)`$ can be precomputed in time $`O(n\mathrm{log}n)`$ that allows this orientation $`G^{}`$ to be computed for any $`𝒜=\{A_i\}`$ in time $`O(_i|A_i|)`$.

Proof:  Reed  gives a recursive $`O(n\mathrm{log}n)`$ algorithm for computing tree decompositions of constant-treewidth graphs based on a linear time algorithm for finding approximate separators for small node subsets. Replacing this separator-finding subroutine with the linear time algorithm of Lipton and Tarjan  gives an $`O(n\mathrm{log}n)`$ time algorithm for computing a tree decomposition of a planar graph. Since each separator has size at most $`k=O(\sqrt{n})`$, the resulting tree decomposition has width at most $`4k=O(\sqrt{n})`$ by Theorem 1 of .

Since all we need to compute a good ordering of $`𝒜`$ is the ordering of the $`n`$ nodes, we can compute this ordering as described in the proof of Theorem 9 and represent it in $`O(n)`$ space by assigning each node an index in the range $`1`$ to $`n`$. Ordering $`𝒜`$ then takes linear time as described in the proof of Theorem 9.

### 3.3 Examples

Applying the results of Sections 3.1 and 3.2 gives:

1. A linear-time algorithm for finding a maximum weight independent set of an interval graph, since $`\beta (G)=1`$ by Lemma 5, and since chordal graphs can be recognized and ordered in linear time using the work of Rose et al. .

While the maximum independent set problem is easily solved for this case (for example, by using the linear time interval graph recognition algorithm of Hsu and Ma  followed by a simple application of dynamic programming) this is an example of how our general method yields good algorithms as special cases.
2. As another special case, a 2-approximation algorithm for interval selection of Berman and DasGupta. Here intervals are partitioned into groups and we must choose non-overlapping intervals with at most one per group. The bid graph $`G`$ is of the form $`G_1G_2`$ where $`G_1`$ is an interval graph and $`G_2`$ is a disjoint union of cliques, one for each group. Thus $`\beta (G)=2`$ by Lemmas 5, 6, and 7.
3. A 3-approximation algorithm for “double auction” interval selection where each interval has both a seller and a buyer, and at most one interval per seller or buyer may be selected. This is the same as the previous case except the graph is now $`G_1G_2G_3`$ where $`G_2`$ and $`G_3`$ are both disjoint unions of cliques.
4. In general, a mechanism for taking *any* bid graph with $`\beta =k`$ and adding up to $`m`$ such unique-selection constraints to get a $`(k+m)`$-approximation algorithm by repeated applications of Lemmas 6 and 7. So for example we get a 3-approximation algorithm for maximum weight three-dimensional matching and a 4-approximation algorithm for auctioning off tracts of undeveloped land spanning intervals where each tract must be acceptable to a seller who provides it, a builder who will develop it, and a buyer who will ultimately purchase both the land and the buildings developed on it.
5. An algorithm to $`k`$-approximate a maximum weight independent set of any subgraph of a $`k`$-dimensional rectangular grid. Orient each edge to leave the point whose coordinates have a smaller sum, giving $`\beta k`$.
6. A linear-time algorithm for $`2`$-approximating a maximum weight independent set of the intersection graph of intervals on a cycle. This follows from Lemma 8: order connected node subsets by inclusion, extend to a linear order $``$, and observe that if $`AB`$ and $`A`$ intersects $`B`$ then $`B`$ intersects one of $`A`$’s two endpoints.555One can do better by breaking the cycle to reduce it to a standard interval graph problem (see, for example, the approach taken by ), but the $`2`$-approximation shows how one can still do reasonably well with our general algorithms Opcost and LR-Opcost.
7. An algorithm for intersection graphs of bounded-height rectangles in a discrete 2D grid. Order the rectangles by their largest $`x`$-coordinate, and make the rightmost grid points of each rectangle be its frontier set in the sense of Lemma 8. If each rectangle is at most $`h`$ tall, there are at most $`h`$ grid points in each frontier. This generalizes in the obvious way to higher dimensions given bounds on all but one of the coordinates, in which case the approximation ratio becomes the product of the bounds.

### 3.4 Hardness of computing $`\beta `$

The difficulty of even approximating the independence number of a graph extends to the directed local independence number.

###### Theorem 11

Any algorithm that can approximate $`\beta (G)`$ for an $`n`$-node directed acyclic graph $`G`$ with a ratio of $`f(n)`$ can be used to approximate the size $`\alpha (H)`$ of a maximum independent set of an undirected $`n`$-node graph $`H`$ with ratio $`f(n+1)`$. Thus by Håstad’s bound on approximating a maximum clique , we cannot approximate $`\beta `$ by $`O(n^{1ϵ})`$ unless $`P=NP`$.

Proof:  Given an undirected $`n`$-node graph $`H`$, construct an $`(n+1)`$-node directed acyclic graph $`G`$ by (a) directing the edges of $`H`$ in any consistent order, and (b) adding a new source node $`s`$ to $`H`$ with edges from $`s`$ to every node in $`H`$.

Let $`I`$ be an independent set in $`H`$. Then every node in $`I`$ is a successor of $`s`$ in $`G`$, and furthermore these nodes are all independent. It follows that $`\beta (G)\beta (s)\alpha (H)`$.

Conversely, if $`I^{}`$ is an independent set of successors of some node $`v`$ in $`H`$, it cannot contain $`s`$ (since $`s`$ is not a successor of any node), and thus $`I^{}`$ is also an independent set in $`H`$. So we have $`\alpha (H)\beta (G)`$.

### 3.5 Effects of node ordering

The performance of the opportunity cost algorithm is strongly sensitive to the order in which the nodes are processed, as this affects the value of $`\beta (u)`$ for each node $`u`$. For many of the examples given in the Section 3.3, a good ordering is provided by the structure of the problem. But what happens in a general graph?

###### Theorem 12

For any graph $`G`$ with given weights, there exists an orientation $`G^{}`$ of $`G`$ for which both Opcost and LR-Opcost output a maximum independent set of $`G`$.

Proof:  Let $`A`$ be any independent set in $`G`$. Choose the ordering so that all nodes in $`A`$ precede all nodes not in $`A`$. Then for any $`uA`$, $`u`$ has no predecessors in the oriented graph and $`value(u)=weight(u)`$.

Let $`A^{}`$ be the independent set computed by the algorithm. If $`u`$ is in $`A`$ but not $`A^{}`$, it must have a successor $`v`$ in $`A^{}A`$ with non-negative value. Since the value of each $`v`$ is its weight less the weight of all its neighbors in $`A`$, the total weight of all elements of $`A^{}A`$ must exceed the total weight of all elements in $`AA^{}`$, and we have $`weight(A^{})=weight(A^{}A)+weight(A^{}A)weight(AA^{})+weight(A^{}A)=weight(A)`$.

In a sense what Theorem 12 shows is that finding a good ordering of a general graph is equivalent to solving the maximum weight independent set problem. This is not surprising since evaluating $`\beta (u)`$ for even a single node $`u`$ requires solving this problem. It follows that to get small approximation ratios we really do need to exploit some special property of the given graph.

In the other direction, we can show that there exist orderings that are not very good:

###### Theorem 13

If all nodes in a graph $`G`$ have distinct weights, orienting $`G`$ in order of decreasing weight causes Opcost and LR-Opcost to return the same independent set as the greedy algorithm.

Proof:  We will prove the result for Opcost; by Theorem 2 the same result holds for LR-Opcost.

Let $`\pi `$ order the nodes in order of decreasing weight. Let us show by induction on $`\pi `$ that if the greedy algorithm chooses a node $`v`$, then $`value(v)=weight(v)`$; but if the greedy algorithm does not choose $`v`$, then $`value(v)<0`$. Suppose we are processing some node $`v`$ and that this induction hypothesis holds for all nodes previously processed. If the greedy algorithm picks $`v`$, then all $`v`$’s predecessors were not chosen and have negative value, and $`value(v)=weight(v)`$. If the greedy algorithm does not pick $`v`$, it is because it chose some $`uv`$; now $`value(v)weight(v)value(u)=weight(v)weight(u)<0`$.

Since the only nodes with non-negative weights are those chosen by the greedy algorithm, Opcost selects them as its output.

## 4 Auctions with budget constraints

Consider the following bidding scenarios:

1. A bidder whose car has broken down wants to buy either a new engine, a new car, or an umbrella and a taxi ride home, but doesn’t particularly care which. However, she has no interest in winning more than one of these bids.
2. Another bidder wants to buy at most three 1968 Volkswagen Beetle hood ornaments, but she would like to bid on all that are available so as not to miss any.
3. Yet another bidder has only $100 in cash, but would like to place multiple bids totaling more than $100, with the understanding that she can only win bids up to her budget.

All of these are examples of *budget constraints*, in which bids in some group consume a common scarce resource. We would like to extend our algorithms to handle such constraints, which are natural in real-world bidding situations.

The first scenario is an example of a *1-of-$`n`$* constraint, where at most one of a set of $`n`$ bids can be accepted. This special case can be handled by modifying $`G`$ by forming a clique out of all bids in each set $`S_i`$; under the assumption that the $`S_i`$ are disjoint, this increases $`\beta `$ by at most $`1`$ (using Lemmas 6 and 7). The second scenario depicts a more general *$`k`$-of-$`n`$* constraint. Such constraints are handled by extending our algorithms to account for the possible revenue loss from bids that cannot be selected because the budget constraint has been exceeded. Again, the approximation ratio rises by $`1`$. We refer to both 1-of-$`n`$ and $`k`$-of-$`n`$ constraints as *unweighted budget constraints*, as each bid consumes a single unit of the budget.

*Weighted budget constraints*, exemplified by the third scenario, are more complicated. With such constraints, we must ensure that the sum of the weights of accepted bids in some group $`S`$ is at most some bound $`b`$. A complication arises because a maximal allowed set of bids might only fill half of a budget limit. With some additional modifications to our algorithms, we get a performance bound of $`2\beta +3`$.

### 4.1 Unweighted budget constraints

Suppose the bids are partitioned into groups $`S_1,\mathrm{},S_r`$ and that no more than $`k_i`$ bids may be selected from $`S_i`$, for $`1ir`$. For each bid $`u`$, let $`g(u)`$ denote the index of the group to which $`u`$ belongs and let $`S_u=S_{g(u)}`$ and $`k_u=k_{g(u)}`$.

Unweighted-Opcost is an extension of Opcost to handle unweighted budget constraints. It has a similar two-step structure.

In the first step, like OC1, we traverse the nodes in topological order and compute a value for each node. We must extend the definition of value for each node to account for the *possible* revenue loss from previously processed bids that may not be selected in the second step because of the budget constraint:

$$value(u)=weight(u)\underset{vu}{}\mathrm{max}(0,value(v))\frac{1}{k_u}\underset{vS_u\{u\},v<u}{}\mathrm{max}(0,value(v)),$$
(3)
where the notation $`v<u`$ means that $`v`$ has already been processed (before $`u`$). Note that the inclusion of $`u`$ in the set of winning bids does not necessarily preclude previously processed bids in $`S_u`$ from also being selected—they may also be selected if the budget $`k_u`$ allows. The coefficient $`\frac{1}{k_u}`$ scales the opportunity cost to account for this fact.

In the second step, like OC2, we traverse the bid graph in reverse topological order, selecting nodes of positive value whose addition to those already selected does not violate the independence or budget constraints.

Unweighted-LR-Opcost solves the same problem using the local ratio technique. It follows the same structure as LR-Opcost. We begin by deleting all non-positive weight nodes from the graph. If any nodes remain, we select a node $`u`$ with no predecessors, and decompose the weight function into $`w=w_1+w_2`$. This time, the decomposition must account for bids that are in the same budget group. We define

$$w_1(v)=\{\begin{array}{cc}w(u)\hfill & \text{if }v\{u\}\delta ^+(u)\text{,}\hfill \\ \frac{1}{k_u}w(u)\hfill & \text{if }vS_u\{u\}\text{,}\hfill \\ 0\hfill & \text{otherwise,}\hfill \end{array}$$

and recursively solve the problem using $`w_2`$ as the weight function. After the recursive call, we must decide if we should add $`u`$ to the set of winning bids $`_2`$. In LR-Opcost, we added $`u`$ to $`_2`$ if and only if $`_2\{u\}`$ was an independent set. In this algorithm, we must also ensure that the budget constraints are satisfied before adding $`u`$ to $`_2`$. We say that a set of bids is *feasible* if they form an independent set and the budget constraints are satisfied.

###### Theorem 14

Given a directed bid graph $`G`$, a partition of the nodes of $`G`$ into nonempty subsets $`S_1,\mathrm{},S_r`$, and an unweighted budget constraint $`k_i`$ for each $`S_i`$,

1. Unweighted-Opcost and Unweighted-LR-Opcost return the same approximation to a revenue maximizing set of bids.
2. Unweighted-Opcost and Unweighted-LR-Opcost $`(\beta (G)+1)`$-approximate an optimal set of bids.
3. Unweighted-Opcost and Unweighted-LR-Opcost run in time linear in the size of $`G`$.

Proof:  The proof that both algorithms return the same approximation is similar to the proof of Theorem 2.

The proof of the approximation ratio follows the same structure as the proof of Theorem 3. We prove the result for Unweighted-LR-Opcost. By Lemma 1, we need only show that the returned set of bids $``$ is a $`(\beta +1)`$-approximation with respect to $`w_2`$ and $`w_1`$. We do this using induction on the recursion. The fact that $``$ is a $`(\beta +1)`$-approximation with respect to $`w_2`$ follows trivially from the inductive assumption.

In the case of $`w_1`$, we will derive an upper bound $`U`$ on the maximum $`w_1`$-weight of a set of feasible bids and a lower bound $`L`$ on the $`w_1`$-weight of any *$`u`$-maximal* set of bids. A $`u`$-maximal set of bids either contains $`u`$ or adding $`u`$ to it would violate the feasibility constraints. In the case of a set of feasible bids, its total $`w_1`$-weight is at most $`\beta (u)w(u)+\frac{k_u}{k_u}w(u)w(u)(\beta +1)=U`$, since the only nonzero contribution to $`w_1`$-weight comes from $`\delta ^+(u)`$ and $`S_u`$. In the case of a $`u`$-maximal set of bids, if $`u`$ cannot be added to the set, then either (1) a successor of $`u`$ is already in the set, in which case the total $`w_1`$-weight is at least $`w(u)`$, or (2) the budget constraint is exceeded, in which case the total $`w_1`$-weight is at least $`w(u)`$. Therefore, the $`w_1`$-weight of these bids is at least $`w(u)`$ and the $`w_1`$ performance bound is

$$\frac{U}{L}=\frac{w(u)(\beta +1)}{w(u)}=\beta +1.$$

The proof of the running time is similar to the proof of Theorem 4. All of the steps that Unweighted-Opcost and Unweighted-LR-Opcost share with Opcost and LR-Opcost take linear time. Unweighted-Opcost adds the cost of computing the last term in (3). Storing $`_{vS_i}\mathrm{max}(0,value(v))`$ in a variable $`\mathrm{\Delta }_{S_i}`$ for each $`S_i`$ allows this term to be computed in time $`O(1)`$ for each node, with an additional $`O(1)`$ cost per node to update the appropriate $`S_i`$. The same technique allows budget constraints to be tested in $`O(1)`$ time per node during the second step. Thus the additional time is linear.

The corresponding modification to Unweighted-LR-Opcost similarly adds only linear time. Rather than updating the weight of each node $`v`$ before each recursive call, we will compute the “current” weight of each node $`v`$ as it is required, subtracting off the total weight $`\mathrm{\Delta }_{S_v}`$ of all previously-processed nodes in $`S_v`$ as in Unweighted-Opcost.

### 4.2 Overlapping unweighted constraints

The analysis in Section 4.1 assumes that the budget constraints partition the bids. For some applications (e.g., bids involving matching up buyers with sellers), we may have overlapping constraints. Overlapping constraints may also be used to handle bids for identical items in limited supply, by grouping all bids asking for copies of the same item together. The algorithms described above can be generalized to handle overlapping constraints.

Suppose we have a family of $`r`$ sets of bids $`𝒮=\{S_1,\mathrm{},S_r\}`$, that each bid appears in at most $`t`$ of these sets, and that at most $`k_i`$ bids may be accepted from set $`S_i`$.

In Overlapping-Unweighted-Opcost, when computing the value of a node $`u`$, we need to account for the possible revenue loss from nodes in each set that $`u`$ belongs to:

$$value(u)=weight(u)\underset{vu}{}\mathrm{max}(0,value(v))\underset{1ir,uS_i}{}\left(\frac{1}{k^i}\underset{vS_u,v<u}{}\mathrm{max}(0,value(v))\right).$$

The rest of the algorithm is the same as Unweighted-Opcost.

In Overlapping-Unweighted-LR-Opcost, the only change from Unweighted-LR-Opcost is in the decomposition of the weight function. We decompose it as

$$w_1(v)=\{\begin{array}{cc}w(u)\hfill & \text{if }v\{u\}\delta ^+(u)\text{,}\hfill \\ _{1ir,u,vS_i}\frac{1}{k_i}w(u)\hfill & \text{if there exist }S_i\text{ containing both }u\text{ and }v\text{,}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

###### Theorem 15

Given a directed bid graph $`G=(V,E)`$, a family of nonempty node subsets $`S_1,\mathrm{},S_r`$, where each node appears in at most $`t`$ of the $`S_i`$, and an unweighted budget constraint $`k_i`$ for each $`S_i`$,

1. Overlapping-Unweighted-Opcost and Overlapping-Unweighted-LR-Opcost return the same approximation to a revenue maximizing set of bids.
2. Overlapping-Unweighted-Opcost and Overlapping-Unweighted-LR-Opcost $`(\beta (G)+t)`$-approximate an optimal set of bids.
3. Overlapping-Unweighted-Opcost and Overlapping-Unweighted-LR-Opcost run in time $`O(|V|t+|E|)`$

Proof:  Similar to the proof of Theorem 14. The additional $`O(|V|t)`$ term comes from having to apply up to $`t`$ budget constraints to each node; since $`_i|S_i||V|t`$, this term also covers the cost of reading the $`S_i`$ from the input and initializing the variables for each subset.

### 4.3 Weighted budget constraints

Suppose that bids are partitioned into groups $`S_1,\mathrm{},S_r`$ and that the total value of the winning bids from group $`i`$ can be no more than $`b_i`$. For each bid $`u`$, let $`g(u)`$ denote the index of the group to which $`u`$ belongs and let $`S_u=S_{g(u)}`$ and $`b_u=b_{g(u)}`$.

This case is more complicated than the unweighted case. The difficulty arises when estimating a lower bound on the $`w_1`$-weight of a $`u`$-maximal set of bids $`S`$. If $`u`$ cannot be added to the set because the budget constraint will be exceeded, the $`w_1`$-weight of $`S`$ can be as small as $`ϵ`$, if $`w_1(u)=b_u`$.

We will describe changes required to LR-Opcost to handle this case. Corresponding changes can be made to Opcost. We will run variations of the algorithm twice, once for the *heavy* bids $`v`$ with $`w(v)>\frac{1}{2}b_v`$ and once for the *light* bids $`v`$ with $`w(v)\frac{1}{2}b_v`$. We then return the better of the two solutions.

In Heavy-Weighted-LR-Opcost, we put an unweighted budget constraint of 1 on each bidder and run Unweighted-LR-Opcost.

###### Lemma 16

Heavy-Weighted-LR-Opcost $`(\beta +1)`$-approximates an optimal set of heavy bids.

Proof:  Since each heavy bid consumes more than half a bidder’s budget, each bidder can win at most one bid. This is just a simple unweighted budget constraint and can be solved as described in Section 4.1 for a performance bound of $`\beta +1`$.

In Light-Weighted-LR-Opcost, when decomposing the weight function, we set

$$w_1(v)=\{\begin{array}{cc}w(u)\hfill & \text{if }v\{u\}\delta ^+(u)\text{,}\hfill \\ \frac{2}{b_u}w(v)w(u)\hfill & \text{if }vS_u\{u\}\text{,}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

Before adding $`u`$ to the winning set of bids $`_2`$, we must ensure that it does not conflict with other bids in $`_2`$ and that the weighted budget constraint is not violated. The rest of the algorithm is identical to LR-Opcost.

###### Lemma 17

Light-Weighted-LR-Opcost $`(\beta +2)`$-approximates an optimal set of light bids.

Proof:  This proof uses the same structure and notation as the proof of Theorem 14. An upper bound $`U`$ on the $`w_1`$-revenue of any feasible set of bids is $`w(u)(\beta +2)`$. With regards to a $`u`$-maximal set of bids, if $`u`$ cannot be added to the set because the budget constraint $`b_u`$ will be exceeded, the existing bids in the set must have weight at least $`b_u/2`$, since $`w(u)b_u/2`$. A lower bound $`L`$ on the $`w_1`$-revenue of any $`u`$-maximal set of bids is therefore $`w(u)`$. The performance bound of this algorithm is $`\frac{U}{L}=\beta +2`$, as claimed.

###### Theorem 18

Given a directed bid graph $`G`$, a partition of the nodes of $`G`$ into nonempty subsets $`S_1,\mathrm{},S_r`$, and a weighted budget constraint $`b_i`$ for each $`S_i`$,

1. Weighted-Opcost and Weighted-LR-Opcost return the same approximation to a revenue maximizing set of bids.
2. Weighted-Opcost and Weighted-LR-Opcost $`(2\beta (G)+3)`$-approximate an optimal set of bids.
3. Weighted-Opcost and Weighted-LR-Opcost run in time linear in the size of $`G`$.

Proof:  The sum of the optimal revenues for the heavy and light bids is at least equal to the optimum revenue among all bids. From Lemmas 16 and 17, the better of the two solutions will be within a factor of $`2\beta +3`$ of the optimum for the general problem.

For the running time, observe that decomposing the bids into heavy and light bids takes linear time, that Heavy-Weighted-Opcost and Heavy-Weighted-LR-Opcost are equivalent to Unweighted-Opcost and Unweighted-LR-Opcost and thus take linear time by Theorem 14, and that Light-Weighted-Opcost and Light-Weighted-LR-Opcost can be made to run in linear time using techniques similar to those used for Unweighted-Opcost and Unweighted-LR-Opcost.

## 5 Further Research

This paper opens up several directions for further research. An immediate open problem is whether overlapping weighted budget constraints can be processed as efficiently as their unweighted counterparts are processed in Theorem 15.

It would be of importance to compare the performance of our algorithms and others in practice. The comparison could be conducted on simulations, but it would be more useful to analyze the performance on real auction data.

As the examples of car sales and land sales demonstrate, topological structures exist in actual bids. Another good example is the FCC auction of airwaves in 1994 and 1995 , where each trading area is an auction object, the trading areas form a plane graph, and bidders prefer to acquire contiguous trading areas. It would be useful to examine past auctions to determine whether similar connectivity structures exist and how such structures affect the computational complexity of bidding strategies and winner determination.