text: The SDDP algorithm converges almost surely on a ﬁnite scenario tree [13, 46] (see also [32, 38] for related results). In some cases, such as additive dependence [27] and Markov dependence [37], the assumption of stage-wise independence can be satisﬁed via an appro- priate reformulation, e.g., see Example 10 in [47]. However, such reformulations are not applicable for stage-wise dependence of random recourse matrices (i.e., in the coeﬃcients of the constraints). Similar approaches that exploit stage-wise independence and value func- tion approximations include multi-stage stochastic decomposition [44] and approximate dynamic programming [40]. An alternative approach to handling the complexity of MSLP is to restrict the functional form of the policy. One such approach is the use of linear decision rules (LDRs). The idea of an LDR is to require that all decisions made in each stage be a linear (or aﬃne) function of the observed random outcomes up to that stage. The problem then reduces to a static problem of ﬁnding the best LDR, whose expected cost then yields an upper bound on the optimal value of the MSLP. In this paper, we refer this use of LDR as a static LDR. While LDRs have a long history (see, e.g., [18]), they have recently gained renewed interest in the mathematical optimization literature after their application to adjustable robust optimization in [4]. The adaptation of this approach to MSLP was presented in [50], and Kuhn et al. [29] analyzed the application of a static LDR in the dual of the MSLP, which then yields a lower bound on the optimal value of the MSLP. Moreover, under certain assumptions, the static approximations obtained after restricting the primal and dual policies to be LDR are both tractable linear programs, as shown in [50] and [29], respectively. The assumptions include stage-wise independence (or a slight generalization), compact and polyhedral support, and ﬁxed recourse (i.e., uncertainty is limited to the right-hand side of the constraints). While in some cases static LDR policies provide high quality approximations to MSLP, they have potential to be signiﬁcantly suboptimal. Better policies (primal and dual) can be obtained by considering more ﬂexible (nonlinear) rules such as (static) piecewise linear decision rules [12] and polynomial decision rules [3]. We propose a new use of LDR, which we refer to as two-stage linear decision rules. The key idea is to partition the decision variables into state and recourse decision variables, with the property that if the state variables are ﬁxed, then the problem decouples into a separate problem for each stage, involving only recourse decision variables. If one applies an LDR only to the state variables, then the problem reduces to a two-stage stochastic linear program (2SLP), in contrast to a static problem which is obtained when using a static LDR. The advantage of two-stage LDRs is that they free the recourse variables from 3

text: The

text: SDDP

text: algorithm

text: converges

text: almost

text: surely

text: on

text: a

text: ﬁnite

text: scenario

text: tree

text: (see

text: also

text: for

text: related

text: results).

text: In

text: some

text: cases,

text: such

text: as

text: additive

text: dependence

text: and

text: Markov

text: dependence

text: the

text: assumption

text: of

text: stage-wise

text: independence

text: can

text: be

text: satisﬁed

text: via

text: an

text: appro-

text: priate

text: reformulation,

text: e.g.,

text: see

text: Example

text: in

text: However,

text: such

text: reformulations

text: are

text: not

text: applicable

text: for

text: stage-wise

text: dependence

text: of

text: random

text: recourse

text: matrices

text: (i.e.,

text: in

text: the

text: coeﬃcients

text: of

text: the

text: constraints).

text: Similar

text: approaches

text: that

text: exploit

text: stage-wise

text: independence

text: and

text: value

text: func-

text: tion

text: approximations

text: include

text: multi-stage

text: stochastic

text: decomposition

text: and

text: approximate

text: dynamic

text: programming

text: An

text: alternative

text: approach

text: to

text: handling

text: the

text: complexity

text: of

text: MSLP

text: is

text: to

text: restrict

text: the

text: functional

text: form

text: of

text: the

text: policy.

text: One

text: such

text: approach

text: is

text: the

text: use

text: of

text: linear

text: decision

text: rules

text: (LDRs).

text: The

text: idea

text: of

text: an

text: LDR

text: is

text: to

text: require

text: that

text: all

text: decisions

text: made

text: in

text: each

text: stage

text: be

text: a

text: linear

text: (or

text: aﬃne)

text: function

text: of

text: the

text: observed

text: random

text: outcomes

text: up

text: to

text: that

text: stage.

text: The

text: problem

text: then

text: reduces

text: to

text: a

text: static

text: problem

text: of

text: ﬁnding

text: the

text: best

text: LDR,

text: whose

text: expected

text: cost

text: then

text: yields

text: an

text: upper

text: bound

text: on

text: the

text: optimal

text: value

text: of

text: the

text: MSLP.

text: In

text: this

text: paper,

text: we

text: refer

text: this

text: use

text: of

text: LDR

text: as

text: a

text: static

text: LDR.

text: While

text: LDRs

text: have

text: a

text: long

text: history

text: (see,

text: e.g.,

text: they

text: have

text: recently

text: gained

text: renewed

text: interest

text: in

text: the

text: mathematical

text: optimization

text: literature

text: after

text: their

text: application

text: to

text: adjustable

text: robust

text: optimization

text: in

text: The

text: adaptation

text: of

text: this

text: approach

text: to

text: MSLP

text: was

text: presented

text: in

text: and

text: Kuhn

text: et

text: al.

text: analyzed

text: the

text: application

text: of

text: a

text: static

text: LDR

text: in

text: the

text: dual

text: of

text: the

text: MSLP,

text: which

text: then

text: yields

text: a

text: lower

text: bound

text: on

text: the

text: optimal

text: value

text: of

text: the

text: MSLP.

text: Moreover,

text: under

text: certain

text: assumptions,

text: the

text: static

text: approximations

text: obtained

text: after

text: restricting

text: the

text: primal

text: and

text: dual

text: policies

text: to

text: be

text: LDR

text: are

text: both

text: tractable

text: linear

text: programs,

text: as

text: shown

text: in

text: and

text: respectively.

text: The

text: assumptions

text: include

text: stage-wise

text: independence

text: (or

text: a

text: slight

text: generalization),

text: compact

text: and

text: polyhedral

text: support,

text: and

text: ﬁxed

text: recourse

text: (i.e.,

text: uncertainty

text: is

text: limited

text: to

text: the

text: right-hand

text: side

text: of

text: the

text: constraints).

text: While

text: in

text: some

text: cases

text: static

text: LDR

text: policies

text: provide

text: high

text: quality

text: approximations

text: to

text: MSLP,

text: they

text: have

text: potential

text: to

text: be

text: signiﬁcantly

text: suboptimal.

text: Better

text: policies

text: (primal

text: and

text: dual)

text: can

text: be

text: obtained

text: by

text: considering

text: more

text: ﬂexible

text: (nonlinear)

text: rules

text: such

text: as

text: (static)

text: piecewise

text: linear

text: decision

text: rules

text: and

text: polynomial

text: decision

text: rules

text: We

text: propose

text: a

text: new

text: use

text: of

text: LDR,

text: which

text: we

text: refer

text: to

text: as

text: two-stage

text: linear

text: decision

text: rules.

text: The

text: key

text: idea

text: is

text: to

text: partition

text: the

text: decision

text: variables

text: into

text: state

text: and

text: recourse

text: decision

text: variables,

text: with

text: the

text: property

text: that

text: if

text: the

text: state

text: variables

text: are

text: ﬁxed,

text: then

text: the

text: problem

text: decouples

text: into

text: a

text: separate

text: problem

text: for

text: each

text: stage,

text: involving

text: only

text: recourse

text: decision

text: variables.

text: If

text: one

text: applies

text: an

text: LDR

text: only

text: to

text: the

text: state

text: variables,

text: then

text: the

text: problem

text: reduces

text: to

text: a

text: two-stage

text: stochastic

text: linear

text: program

text: in

text: contrast

text: to

text: a

text: static

text: problem

text: which

text: is

text: obtained

text: when

text: using

text: a

text: static

text: LDR.

text: The

text: advantage

text: of

text: two-stage

text: LDRs

text: is

text: that

text: they

text: free

text: the

text: recourse

text: variables

text: from


text: In future research it will be interesting to test the use of two-stage LDR on more prob- lems, and to investigate if there are problem classes where two-stage LDR yields policies that are provably optimal or near-optimal. As we mentioned in the introduction, in the primal problem, two-stage LDR can be directly applied to multi-stage stochastic mixed integer programs, provided the integrality restrictions are imposed only on the recourse variables. Since availability of algorithms for multi-stage stochastic mixed integer programs is very limited, it will be interesting to ex- plore this extension further, in particular possibly using ideas from [6] to obtain a decision rule in the case the state variables also have integrality constraints. Acknowledgements. This work is supported in part by the National Science Foundation un- der grant CMMI-1634597, and by the U.S. Department of Energy, Oﬃce of Science, Oﬃce of Advanced Scientiﬁc Computing Research, Applied Mathematics program under contract number DE-AC02-06CH11357. References [1] S. Ahmed. Multistage stochastic optimization. https://www.ima.umn.edu/materials/ 2015-2016/ND8.1-12.16/25386/mssp.pdf. New Directions Short Course on Mathematical Optimization, 2016. [2] I. Bakir, N. Boland, B. Dandurand, and A. Erera. Scenario set partition dual bounds for multistage stochastic programming: A hierarchy of bounds and a partition sampling approach, 2016. http://www.optimization-online.org/DB_FILE/2016/01/5311.pdf. [3] D. Bampou and D. Kuhn. Scenario-free stochastic programming with polynomial decision rules. In 2011 50th IEEE Conference on Decision and Control and European Control Conference, pages 7806–7812. IEEE, 2011. [4] A. Ben-Tal, A. Goryashko, E. Guslitzer, and A. Nemirovski. Adjustable robust solutions of uncertain linear programs. Math. Program., 99(2):351–376, 2004. [5] D. Bertsimas and C. Caramanis. Adaptability via sampling. In Decision and Control, 2007 46th IEEE Conference on, pages 4717–4722. IEEE, 2007. [6] D. Bertsimas and A. Georghiou. Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Oper. Res., 63(3):610–627, 2015. [7] J.R. Birge. Aggregation bounds in stochastic linear programming. Math. Program., 31(1):25– 41, 1985. [8] J.R. Birge. Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res., 33(5):989–1007, 1985. 26

text: In

label: paragraph

text: future

text: research

text: it

text: will

text: be

text: interesting

text: to

text: test

text: the

text: use

text: of

text: two-stage

text: LDR

text: on

text: more

text: prob-

text: lems,

text: and

text: to

text: investigate

text: if

text: there

text: are

text: problem

text: classes

text: where

text: two-stage

text: LDR

text: yields

text: policies

text: that

text: are

text: provably

text: optimal

text: or

text: near-optimal.

text: As

text: we

text: mentioned

text: in

text: the

text: introduction,

text: in

text: the

text: primal

text: problem,

text: two-stage

text: LDR

text: can

text: be

text: directly

text: applied

text: to

text: multi-stage

text: stochastic

text: mixed

text: integer

text: programs,

text: provided

text: the

text: integrality

text: restrictions

text: are

text: imposed

text: only

text: on

text: the

text: recourse

text: variables.

text: Since

text: availability

text: of

text: algorithms

text: for

text: multi-stage

text: stochastic

text: mixed

text: integer

text: programs

text: is

text: very

text: limited,

text: it

text: will

text: be

text: interesting

text: to

text: ex-

text: plore

text: this

text: extension

text: further,

text: in

text: particular

text: possibly

text: using

text: ideas

text: from

text: to

text: obtain

text: a

text: decision

text: rule

text: in

text: the

text: case

text: the

text: state

text: variables

text: also

text: have

text: integrality

text: constraints.

text: Acknowledgements.

text: This

text: work

text: is

text: supported

text: in

text: part

text: by

text: the

text: National

text: Science

text: Foundation

text: un-

text: der

text: grant

text: and

text: by

text: the

text: U.S.

text: Department

text: of

text: Energy,

text: Oﬃce

text: of

text: Science,

text: Oﬃce

text: of

text: Advanced

text: Scientiﬁc

text: Computing

text: Research,

text: Applied

text: Mathematics

text: program

text: under

text: contract

text: number

text: References

text: S.

text: Ahmed.

text: Multistage

text: stochastic

text: optimization.

text: New

text: Directions

text: Short

text: Course

text: on

text: Mathematical

text: Optimization,

text: I.

text: Bakir,

text: N.

text: Boland,

text: B.

text: Dandurand,

text: and

text: A.

text: Erera.

text: Scenario

text: set

text: partition

text: dual

text: bounds

text: for

text: multistage

text: stochastic

text: programming:

text: A

text: hierarchy

text: of

text: bounds

text: and

text: a

text: partition

text: sampling

text: approach,

text: D.

text: Bampou

text: and

text: D.

text: Kuhn.

text: Scenario-free

text: stochastic

text: programming

text: with

text: polynomial

text: decision

text: rules.

text: In

text: IEEE

text: Conference

text: on

text: Decision

text: and

text: Control

text: and

text: European

text: Control

text: Conference,

text: pages

text: IEEE,

text: A.

text: Ben-Tal,

text: A.

text: Goryashko,

text: E.

text: Guslitzer,

text: and

text: A.

text: Nemirovski.

text: Adjustable

text: robust

text: solutions

text: of

text: uncertain

text: linear

text: programs.

text: Math.

text: Program.,

text: D.

text: Bertsimas

text: and

text: C.

text: Caramanis.

text: Adaptability

text: via

text: sampling.

text: In

text: Decision

text: and

text: Control,

text: IEEE

text: Conference

text: on,

text: pages

text: IEEE,

text: D.

text: Bertsimas

text: and

text: A.

text: Georghiou.

text: Design

text: of

text: near

text: optimal

text: decision

text: rules

text: in

text: multistage

text: adaptive

text: mixed-integer

text: optimization.

text: Oper.

text: Res.,

text: J.R.

text: Birge.

text: Aggregation

text: bounds

text: in

text: stochastic

text: linear

text: programming.

text: Math.

text: Program.,

text: J.R.

text: Birge.

text: Decomposition

text: and

text: partitioning

text: methods

text: for

text: multistage

text: stochastic

text: linear

text: programs.

text: Oper.

text: Res.,


text: integrality restrictions are imposed only on the recourse variables. When the state variables have integrality restrictions as well, the form of the decision rule applied to the state variables must be modiﬁed, but the two-stage approach still applies. We refer to [6] for one possible such decision rule based on piecewise-linear binary functions. We remark that combining our approach with that of [6] would have potential beneﬁt in terms of both tractability and policy quality, as removing the piecewise-linear binary decision rule requirement from the recourse variables both eliminates the need to design such a rule, and gives those decisions more ﬂexibility. The rest of this paper is organized as follows. Section deﬁnes the MSLP, reviews the static LDR approach, and presents the proposed two-stage LDR approach, including discussion of how to solve the approximate problem and obtain statistical upper bounds on the original MSLP. Section conducts a similar analysis for the dual of an MSLP, yielding an approach for ﬁnding statistical lower bounds on an MSLP. We present an illustrative application in Section and make concluding remarks in Section . 2 Primal two-stage linear decision rules ≥ We formulate an MSLP with T 2 stages as follows, where throughout the paper, for ≤(cid:104) (cid:88) { } (cid:105) { } integers a b, [a, b] := a, a + 1, . . . , b and [b] := 1, . . . , b : E (cid:62) (cid:62) min c (ξt) x (ξt) + h (ξt) s (ξt) (1a) t t t t x,s ∈ t [T] − ∈ P s.t. A (ξt)s (ξt) + B (ξt)s − (ξt 1) + C (ξt)x (ξt) = b (ξt), t [T ], -a.s., (1b) t t t t 1 t t t ≥ ∈ P D (ξt)s (ξt) + E (ξt)x (ξt) d (ξt), t [T ], -a.s., (1c) t t t t t ∈ R ∈ R ∈ P x (ξt) pt, s (ξt) qt, t [T ], -a.s. (1d) t t { } P Here, ξ T is a stochastic process with probability distribution an(cid:80)d support Ξ, where t t=1 ∈ ξ = 1 for all ξ Ξ (i.e., data in stage 1 is deterministic), ξ is a random vector taking values 1 t R ∈ ∈ ∈ in (cid:96)r for t [2, T ], and ξt := (ξ1, . . . , ξt) for t [T ]. We denote (cid:96)t := tr=1 (cid:96)r for t [T ]. The s and x variables are referred to as state and recourse variables, respectively. Similarly, (1b) and (1c) are referred to as state equations and recourse constraints, respectively. The objective is to minimize the expected total cost. The constraints are required to be almost P surely satisﬁed with respect to the distribution of the stochastic process, denoted by “ -a.s.” We note that any MSLP can be brought into the form of (1) by introducing additional variables and constraints. Throughout the paper, we assume that (1) is feasible and has 5

text: integrality

text: restrictions

text: are

text: imposed

text: only

text: on

text: the

text: recourse

text: variables.

text: When

text: the

text: state

text: variables

text: have

text: integrality

text: restrictions

text: as

text: well,

text: the

text: form

text: of

text: the

text: decision

text: rule

text: applied

text: to

text: the

text: state

text: variables

text: must

text: be

text: modiﬁed,

text: but

text: the

text: two-stage

text: approach

text: still

text: applies.

text: We

text: refer

text: to

text: for

text: one

text: possible

text: such

text: decision

text: rule

text: based

text: on

text: piecewise-linear

text: binary

text: functions.

text: We

text: remark

text: that

text: combining

text: our

text: approach

text: with

text: that

text: of

text: would

text: have

text: potential

text: beneﬁt

text: in

text: terms

text: of

text: both

text: tractability

text: and

text: policy

text: quality,

text: as

text: removing

text: the

text: piecewise-linear

text: binary

text: decision

text: rule

text: requirement

text: from

text: the

text: recourse

text: variables

text: both

text: eliminates

text: the

text: need

text: to

text: design

text: such

text: a

text: rule,

text: and

text: gives

text: those

text: decisions

text: more

text: ﬂexibility.

text: The

text: rest

text: of

text: this

text: paper

text: is

text: organized

text: as

text: follows.

text: Section

text: deﬁnes

text: the

text: MSLP,

text: reviews

text: the

text: static

text: LDR

text: approach,

text: and

text: presents

text: the

text: proposed

text: two-stage

text: LDR

text: approach,

text: including

text: discussion

text: of

text: how

text: to

text: solve

text: the

text: approximate

text: problem

text: and

text: obtain

text: statistical

text: upper

text: bounds

text: on

text: the

text: original

text: MSLP.

text: Section

text: conducts

text: a

text: similar

text: analysis

text: for

text: the

text: dual

text: of

text: an

text: MSLP,

text: yielding

text: an

text: approach

text: for

text: ﬁnding

text: statistical

text: lower

text: bounds

text: on

text: an

text: MSLP.

text: We

text: present

text: an

text: illustrative

text: application

text: in

text: Section

text: and

text: make

text: concluding

text: remarks

text: in

text: Section

text: Primal

text: two-stage

text: linear

text: decision

text: rules

text: We

text: formulate

text: an

text: MSLP

text: with

text: T

text: stages

text: as

text: follows,

text: where

text: throughout

text: the

text: paper,

text: for

text: integers

text: a

text: b,

text: [a,

text: b]

text: a,

text: a

text: b

text: and

text: [b]

text: b

text: E

text: min

text: c

text: (ξt)

text: x

text: (ξt)

text: h

text: (ξt)

text: s

text: (ξt)

text: t

text: t

text: t

text: t

text: x,s

text: t

text: [T]

text: P

text: s.t.

text: A

text: (ξt)s

text: (ξt)

text: B

text: (ξt)s

text: (ξt

text: C

text: (ξt)x

text: (ξt)

text: b

text: (ξt),

text: t

text: [T

text: -a.s.,

text: t

text: t

text: t

text: t

text: t

text: t

text: t

text: P

text: D

text: (ξt)s

text: (ξt)

text: E

text: (ξt)x

text: (ξt)

text: d

text: (ξt),

text: t

text: [T

text: -a.s.,

text: t

text: t

text: t

text: t

text: t

text: R

text: R

text: P

text: x

text: (ξt)

text: pt,

text: s

text: (ξt)

text: qt,

text: t

text: [T

text: -a.s.

text: t

text: t

text: P

text: Here,

text: ξ

text: T

text: is

text: a

text: stochastic

text: process

text: with

text: probability

text: distribution

text: support

text: Ξ,

text: where

text: t

text: ξ

text: for

text: all

text: ξ

text: Ξ

text: (i.e.,

text: data

text: in

text: stage

text: is

text: deterministic),

text: ξ

text: is

text: a

text: random

text: vector

text: taking

text: values

text: t

text: R

text: in

text: for

text: t

text: T

text: and

text: ξt

text: ξt)

text: for

text: t

text: [T

text: We

text: denote

text: for

text: t

text: [T

text: The

text: s

text: and

text: x

text: variables

text: are

text: referred

text: to

text: as

text: state

text: and

text: recourse

text: variables,

text: respectively.

text: Similarly,

text: and

text: are

text: referred

text: to

text: as

text: state

text: equations

text: and

text: recourse

text: constraints,

text: respectively.

text: The

text: objective

text: is

text: to

text: minimize

text: the

text: expected

text: total

text: cost.

text: The

text: constraints

text: are

text: required

text: to

text: be

text: almost

text: P

text: surely

text: satisﬁed

text: with

text: respect

text: to

text: the

text: distribution

text: of

text: the

text: stochastic

text: process,

text: denoted

text: by

text: -a.s.”

text: We

text: note

text: that

text: any

text: MSLP

text: can

text: be

text: brought

text: into

text: the

text: form

text: of

text: by

text: introducing

text: additional

text: variables

text: and

text: constraints.

text: Throughout

text: the

text: paper,

text: we

text: assume

text: that

text: is

text: feasible

text: and

text: has


text: Proposition 2.1. The following inequalities hold: ≤ ≤ zMSLP z2S zLDR. The diﬀerence between zLDR and z2S can be arbitrarily large. In particular, an example is given in [18] of a 2SLP having relatively complete recourse for which LDR-LP is infeasible ∞ (zLDR = ), while the 2SLP (and hence LDR-2SLP) is feasible. Unfortunately, the techniques used to derive a static approximation of LDR-LP do not yield an eﬃciently computable reformulation of LDR-2SLP, even under assumptions A1- A4. In the next section, we review approaches for obtaining an approximate solution, say βˆ, of LDR-2SLP. Then, in Section we discuss techniques for estimating an upper bound on zMSLP using such a solution. 2.3 Approximate solution of LDR-2SLP There is a huge literature on (approximately) solving 2SLP problems. In this section, we present a brief overview of relevant approaches, with a focus on identifying the required assumptions. We refer the reader to [48] for more details. A common approach for approximately solving a 2SLP is sample average approximation, P P in which is approximated by a discrete probability measure ˆ that assigns positive weights only to a ﬁnite (relatively small) number of realizations of ξ which are called scenarios. In this way, the intractable expectation term is replaced with a sum. Scenarios may be constructed by a variety of techniques, such as Monte Carlo, quasi-Monte Carlo, and Latin hypercube sampling (e.g., [24, 28, 31, 35, 49]). For the purpose of this paper, we consider only the conceptually simplest case in which scenarios are generated via independent Monte Carlo sampling. Let ξ , j = 1, . . . , N, be an independent and identically distributed (i.i.d.) random sam- j ple of the random vector ξ, and deﬁne the sample average approximation (SAA) problem: 9

text: Proposition

text: The

text: following

text: inequalities

text: hold:

text: zMSLP

text: zLDR.

text: The

text: diﬀerence

text: between

text: zLDR

text: and

text: can

text: be

text: arbitrarily

text: large.

text: In

text: particular,

text: an

text: example

text: is

text: given

text: in

text: of

text: a

text: having

text: relatively

text: complete

text: recourse

text: for

text: which

text: LDR-LP

text: is

text: infeasible

text: (zLDR

text: while

text: the

text: (and

text: hence

text: is

text: feasible.

text: Unfortunately,

text: the

text: techniques

text: used

text: to

text: derive

text: a

text: static

text: approximation

text: of

text: LDR-LP

text: do

text: not

text: yield

text: an

text: eﬃciently

text: computable

text: reformulation

text: of

text: even

text: under

text: assumptions

text: In

text: the

text: next

text: section,

text: we

text: review

text: approaches

text: for

text: obtaining

text: an

text: approximate

text: solution,

text: say

text: βˆ,

text: of

text: Then,

text: in

text: Section

text: we

text: discuss

text: techniques

text: for

text: estimating

text: an

text: upper

text: bound

text: on

text: zMSLP

text: using

text: such

text: a

text: solution.

text: Approximate

text: solution

text: of

text: There

text: is

text: a

text: huge

text: literature

text: on

text: (approximately)

text: solving

text: problems.

text: In

text: this

text: section,

text: we

text: present

text: a

text: brief

text: overview

text: of

text: relevant

text: approaches,

text: with

text: a

text: focus

text: on

text: identifying

text: the

text: required

text: assumptions.

text: We

text: refer

text: the

text: reader

text: to

text: for

text: more

text: details.

text: A

text: common

text: approach

text: for

text: approximately

text: solving

text: a

text: is

text: sample

text: average

text: approximation,

text: P

text: P

text: in

text: which

text: is

text: approximated

text: by

text: a

text: discrete

text: probability

text: measure

text: ˆ

text: that

text: assigns

text: positive

text: weights

text: only

text: to

text: a

text: ﬁnite

text: (relatively

text: small)

text: number

text: of

text: realizations

text: of

text: ξ

text: which

text: are

text: called

text: scenarios.

text: In

text: this

text: way,

text: the

text: intractable

text: expectation

text: term

text: is

text: replaced

text: with

text: a

text: sum.

text: Scenarios

text: may

text: be

text: constructed

text: by

text: a

text: variety

text: of

text: techniques,

text: such

text: as

text: Monte

text: Carlo,

text: quasi-Monte

text: Carlo,

text: and

text: Latin

text: hypercube

text: sampling

text: (e.g.,

text: For

text: the

text: purpose

text: of

text: this

text: paper,

text: we

text: consider

text: only

text: the

text: conceptually

text: simplest

text: case

text: in

text: which

text: scenarios

text: are

text: generated

text: via

text: independent

text: Monte

text: Carlo

text: sampling.

text: Let

text: ξ

text: j

text: N,

text: be

text: an

text: independent

text: and

text: identically

text: distributed

text: (i.i.d.)

text: random

text: sam-

text: j

text: ple

text: of

text: the

text: random

text: vector

text: ξ,

text: and

text: deﬁne

text: the

text: sample

text: average

text: approximation

text: (SAA)

text: problem:


text: Lemma 3.1(f), and at most two fair vertices by Corollary 3.3(a). By Corollary 3.3(b), N ∗(x) G has at most one bad vertex, and if such a bad vertex exists, then has no good or fair N ∗(x) G vertex. Finally, has at most one fair vertex and one good vertex simultaneously by N ∗(x) G ≤ Corollary 3.3(c,d). Thus and when has a bad vertex, as claimed. We t 2 t = 1 N ∗(x) G will redistribute the charges of according to the following discharging rule: x ∈ ∗ ≥ ∗ (R): For each x V (G ) with d ∗(x) = 3 and exactly t 1 neighbors of degree two in G , G ≥ ∗ x sends 1 1 charges to each of its neighbors of degree two in G . 2t 4 ∗ ∗ Let be the new charge of after applying the above discharging rule. We see that ω G ∈ ∗ ∗ ≥ ∈ ∗ for any with , . We next show that for any with v V (G ) d ∗(v) = 3 ω (v) 0 v V (G ) G ∗ ≥ ∈ ∗ , . Let be a vertex with . By Observation and d ∗(v) = 2 ω (v) 0 v V (G ) d ∗(v) = 2 G G | | { } Lemma 3.1(a), . Let . If is good, then N ∗(v) = 2 N ∗(v) = u, w v d ∗(u) = d ∗(w) = 3 G G G G ∗ ≥ by Lemma 3.1(c). Thus . Next, suppose that is bad. We ω (v) ω(v) + 1/4 + 1/4 = 0 v may assume that is bad. By Lemma 3.2(d), . By the above claim, is the only u d ∗(w) = 3 v G ∗ ≥ (bad) vertex of degree two of . By the discharging rule (R), . N ∗(w) ω (v) ω(v) + 1/2 = 0 G Finally, suppose that is a fair vertex. Then . By Lemma 3.1(b), v d (u) = d (w) = 3 G G ∗ ≥ n(cid:80)either u nor w is good. Thus d ∗(u) = d ∗(w(cid:80)) = 3. By the dis(cid:80)charging rule (R), ω (v) G G ∗ ≥ ∈ ∗ . This proves that for any with . Thus ω(v) + 1/4 + 1/4 = 0 ω (v) 0 v V (G ) d ∗(v) = 2 G ∗ ≥ ∗ , contrary to the fact that . ∈ ∗ ω (v) 0 ∈ ∗ ω (v) = ∈ ∗ ω(v) < 0 v V (G ) v V (G ) v V (G ) This completes the proof of Theorem 1.6(c). The proof of Theorem 1.6(b) is similar to the proof Theorem 1.6(c). For its completeness, we include its proof here because the discharging part is diﬀerent and more involved. Suppose the assertion is false. Let be a subcubic multigraph with and is not G mad(G) < 24/11 G | | star -edge-colorable. Among all counterexamples we choose so that is minimum. By 5 G G ∈ the choice of , is connected and star -critical. Clearly, . For all , G G 5 mad(G) < 24/11 i [3] { ∈ } | | ∈ let and let for all . By Lemma 3.1(a), is A = v V (G) : d (v) = i n = A i [3] A i G i i 1 ⊆ ∗ \ ∗ an independent set in and . Let . Then . We G N (A ) A G = G A mad(G ) < 24/11 G 1 3 1 ∗ − − see that and so . 2e(G ) = 2e(G) 2n = 2n + 3n n < 24(n + n )/11 9n < 2n + 11n 1 2 3 1 2 3 3 2 1 ∪ (cid:54) ∅ ∗ ≥ ∈ ∗ Thus . By Lemma 3.1(b), . We say that a vertex with A A = δ(G ) 2 v V (G ) 1 2 is good if ; bad if and is adjacent to another vertex of d ∗(v) = 2 d (v) = 3 d (v) = 2 v G G G { ∈ ∗ } degree two in ; and fair if and is not bad. Let . G d (v) = 2 v B := v V (G ) : d ∗(v) = 2 G G ∗ We next claim that every component of is isomorphic to , or . G [B] K K P 1 2 3 ∗ Suppose not. Let be a longest path in with vertices in order, where P G [B] x , x , . . . , x 1 2 p ≥ ∈ (cid:54) or and or and is a multiple edge. Clearly, by p 4 p = 3 x x E(G) p = 2 x x p = 2 1 3 1 2 13 ##LTLine## ##LTLine##

text: Lemma

text: and

text: at

text: most

text: two

text: fair

text: vertices

text: by

text: Corollary

text: By

text: Corollary

text: N

text: ∗(x)

text: G

text: has

text: at

text: most

text: one

text: bad

text: vertex,

text: and

text: if

text: such

text: a

text: bad

text: vertex

text: exists,

text: then

text: has

text: no

text: good

text: or

text: fair

text: N

text: ∗(x)

text: G

text: vertex.

text: Finally,

text: has

text: at

text: most

text: one

text: fair

text: vertex

text: and

text: one

text: good

text: vertex

text: simultaneously

text: by

text: N

text: ∗(x)

text: G

text: Corollary

text: Thus

text: and

text: when

text: has

text: a

text: bad

text: vertex,

text: as

text: claimed.

text: We

text: t

text: t

text: N

text: ∗(x)

text: G

text: will

text: redistribute

text: the

text: charges

text: of

text: according

text: to

text: the

text: following

text: discharging

text: rule:

text: x

text: (R):

text: For

text: each

text: x

text: V

text: (G

text: with

text: d

text: ∗(x)

text: and

text: exactly

text: t

text: neighbors

text: of

text: degree

text: two

text: in

text: G

text: G

text: x

text: sends

text: charges

text: to

text: each

text: of

text: its

text: neighbors

text: of

text: degree

text: two

text: in

text: G

text: Let

text: be

text: the

text: new

text: charge

text: of

text: after

text: applying

text: the

text: above

text: discharging

text: rule.

text: We

text: see

text: that

text: ω

text: G

text: for

text: any

text: with

text: We

text: next

text: show

text: that

text: for

text: any

text: with

text: v

text: V

text: (G

text: d

text: ∗(v)

text: ω

text: (v)

text: v

text: V

text: (G

text: G

text: Let

text: be

text: a

text: vertex

text: with

text: By

text: Observation

text: and

text: d

text: ∗(v)

text: ω

text: (v)

text: v

text: V

text: (G

text: d

text: ∗(v)

text: G

text: G

text: Lemma

text: Let

text: If

text: is

text: good,

text: then

text: N

text: ∗(v)

text: N

text: ∗(v)

text: u,

text: w

text: v

text: d

text: ∗(u)

text: d

text: ∗(w)

text: G

text: G

text: G

text: G

text: by

text: Lemma

text: Thus

text: Next,

text: suppose

text: that

text: is

text: bad.

text: We

text: ω

text: (v)

text: ω(v)

text: v

text: may

text: assume

text: that

text: is

text: bad.

text: By

text: Lemma

text: By

text: the

text: above

text: claim,

text: is

text: the

text: only

text: u

text: d

text: ∗(w)

text: v

text: G

text: (bad)

text: vertex

text: of

text: degree

text: two

text: of

text: By

text: the

text: discharging

text: rule

text: (R),

text: N

text: ∗(w)

text: ω

text: (v)

text: ω(v)

text: G

text: Finally,

text: suppose

text: that

text: is

text: a

text: fair

text: vertex.

text: Then

text: By

text: Lemma

text: v

text: d

text: (u)

text: d

text: (w)

text: G

text: G

text: u

text: nor

text: w

text: is

text: good.

text: Thus

text: d

text: ∗(u)

text: d

text: By

text: the

text: rule

text: (R),

text: ω

text: (v)

text: G

text: G

text: This

text: proves

text: that

text: for

text: any

text: with

text: Thus

text: ω(v)

text: ω

text: (v)

text: v

text: V

text: (G

text: d

text: ∗(v)

text: G

text: contrary

text: to

text: the

text: fact

text: that

text: ω

text: (v)

text: ω

text: (v)

text: ω(v)

text: v

text: V

text: (G

text: v

text: V

text: (G

text: v

text: V

text: (G

text: This

text: completes

text: the

text: proof

text: of

text: Theorem

text: The

text: proof

text: of

text: Theorem

text: is

text: similar

text: to

text: the

text: proof

text: Theorem

text: For

text: its

text: completeness,

text: we

text: include

text: its

text: proof

text: here

text: because

text: the

text: discharging

text: part

text: is

text: diﬀerent

text: and

text: more

text: involved.

text: Suppose

text: the

text: assertion

text: is

text: false.

text: Let

text: be

text: a

text: subcubic

text: multigraph

text: with

text: and

text: is

text: not

text: G

text: mad(G)

text: G

text: star

text: -edge-colorable.

text: Among

text: all

text: counterexamples

text: we

text: choose

text: so

text: that

text: is

text: minimum.

text: By

text: G

text: G

text: the

text: choice

text: of

text: is

text: connected

text: and

text: star

text: -critical.

text: Clearly,

text: For

text: all

text: G

text: G

text: mad(G)

text: i

text: let

text: and

text: let

text: for

text: all

text: By

text: Lemma

text: is

text: A

text: v

text: V

text: (G)

text: d

text: (v)

text: i

text: n

text: A

text: i

text: A

text: i

text: G

text: i

text: i

text: an

text: independent

text: set

text: in

text: and

text: Let

text: Then

text: We

text: G

text: N

text: (A

text: A

text: G

text: G

text: A

text: mad(G

text: G

text: see

text: that

text: and

text: so

text: n

text: n

text: Thus

text: By

text: Lemma

text: We

text: say

text: that

text: a

text: vertex

text: with

text: A

text: A

text: δ(G

text: v

text: V

text: (G

text: is

text: good

text: if

text: bad

text: if

text: and

text: is

text: adjacent

text: to

text: another

text: vertex

text: of

text: d

text: ∗(v)

text: d

text: (v)

text: d

text: (v)

text: v

text: G

text: G

text: G

text: degree

text: two

text: in

text: and

text: fair

text: if

text: and

text: is

text: not

text: bad.

text: Let

text: G

text: d

text: (v)

text: v

text: B

text: v

text: V

text: (G

text: d

text: ∗(v)

text: G

text: G

text: We

text: next

text: claim

text: that

text: every

text: component

text: of

text: is

text: isomorphic

text: to

text: or

text: G

text: [B]

text: K

text: K

text: P

text: Suppose

text: not.

text: Let

text: be

text: a

text: longest

text: path

text: in

text: with

text: vertices

text: in

text: order,

text: where

text: P

text: G

text: [B]

text: x

text: x

text: x

text: p

text: or

text: and

text: or

text: and

text: is

text: a

text: multiple

text: edge.

text: Clearly,

text: by

text: p

text: p

text: x

text: x

text: E(G)

text: p

text: x

text: x

text: p

text: ##LTLine##

text: ##LTLine##


text: our attention. Yongtang Shi would like to thank Bojan Mohar for his helpful discussion and for mentioning the complexity problem on star edge-coloring during his visit to Simon Fraser University. The authors would like to thank Rong Luo for his helpful comments. References [1] M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen and R. Ramamurthi, Coloring with no 2-colored ’s, Electron. J. Combin. 11 (2004), #R26. P 4 [2] Ľ. Bezegová, B. Lužar, M. Mockovčiaková and R. Soták, R. Škrekovski, Star edge coloring of some classes of graphs, J Graph Theory 81 (2016) 73–82. [3] O. V. Borodin, A. V. Kostochka, J. Nešetřil, A. Raspaud and E. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77–89. [4] Y. Bu, D. W. Cranston, M. Montassier, A. Raspaud and W. Wang, Star coloring of sparse graphs, J Graph Theory 62 (2009) 201–219. [5] M. Chen, A. Raspaud and W. Wang, -star-coloring of subcubic graphs, J Graph 6 Theory 72 (2013) 128–145. [6] Z. Dvořák, B. Mohar and R. Šámal, Star chromatic index, J Graph Theory 72 (2013) 313–326. [7] I. Holyer, The NP-completeness of edge-coloring, SIAM J Comput. 10 (1981) 718–720. [8] S. Kerdjoudj, A. V. Kostochka and A. Raspaud, List star edge coloring of subcubic graphs, to appear in Discuss. Math. Graph Theory. [9] H. A. Kierstead and A. Kündgen, C. Timmons, Star coloring bipartite planar graphs, J Graph Theory 60 (2009) 1–10. [10] X.-S. Liu and K. Deng, An upper bound on the star chromatic index of graphs with ≥ , J Lanzhou Univ (Nat Sci) 44 (2008) 94–95. ∆ 7 [11] J. Nešetřil and P. Ossona de Mendez, Colorings and homomorphisms of minor closed classes, Algorithms and Combinatorics, Vol. 25, Springer, Berlin, 2003, pp. 651–664. [12] K. Pradeep and V. Vijayalakshmi, Star chromatic index of subcubic graphs, Electron. Notes Discrete Math. 53 (2016) 155–164. [13] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret Analiz 3 (1964), 25–30 (in Russian). 15

text: our

text: attention.

text: Yongtang

text: Shi

text: would

text: like

text: to

text: thank

text: Bojan

text: Mohar

text: for

text: his

text: helpful

text: discussion

text: and

text: for

text: mentioning

text: the

text: complexity

text: problem

text: on

text: star

text: edge-coloring

text: during

text: his

text: visit

text: to

text: Simon

text: Fraser

text: University.

text: The

text: authors

text: would

text: like

text: to

text: thank

text: Rong

text: Luo

text: for

text: his

text: helpful

text: comments.

text: References

label: reference

text: M.

text: O.

text: Albertson,

text: G.

text: G.

text: Chappell,

text: H.

text: A.

text: Kierstead,

text: A.

text: Kündgen

text: and

text: R.

text: Ramamurthi,

text: Coloring

text: with

text: no

text: ’s,

text: Electron.

text: J.

text: Combin.

text: P

text: Ľ.

text: Bezegová,

text: B.

text: Lužar,

text: M.

text: Mockovčiaková

text: and

text: R.

text: Soták,

text: R.

text: Škrekovski,

text: Star

text: edge

text: coloring

text: of

text: some

text: classes

text: of

text: graphs,

text: J

text: Graph

text: Theory

text: O.

text: V.

text: Borodin,

text: A.

text: V.

text: Kostochka,

text: J.

text: Nešetřil,

text: A.

text: Raspaud

text: and

text: E.

text: Sopena,

text: On

text: the

text: maximum

text: average

text: degree

text: and

text: the

text: oriented

text: chromatic

text: number

text: of

text: a

text: graph,

text: Discrete

text: Math.

text: Y.

text: Bu,

text: D.

text: W.

text: Cranston,

text: M.

text: Montassier,

text: A.

text: Raspaud

text: and

text: W.

text: Wang,

text: Star

text: coloring

text: of

text: sparse

text: graphs,

text: J

text: Graph

text: Theory

text: M.

text: Chen,

text: A.

text: Raspaud

text: and

text: W.

text: Wang,

text: -star-coloring

text: of

text: subcubic

text: graphs,

text: J

text: Graph

text: Theory

text: Z.

text: Dvořák,

text: B.

text: Mohar

text: and

text: R.

text: Šámal,

text: Star

text: chromatic

text: index,

text: J

text: Graph

text: Theory

text: I.

text: Holyer,

text: The

text: NP-completeness

text: of

text: edge-coloring,

text: SIAM

text: J

text: Comput.

text: S.

text: Kerdjoudj,

text: A.

text: V.

text: Kostochka

text: and

text: A.

text: Raspaud,

text: List

text: star

text: edge

text: coloring

text: of

text: subcubic

text: graphs,

text: to

text: appear

text: in

text: Discuss.

text: Math.

text: Graph

text: Theory.

text: H.

text: A.

text: Kierstead

text: and

text: A.

text: Kündgen,

text: C.

text: Timmons,

text: Star

text: coloring

text: bipartite

text: planar

text: graphs,

text: J

text: Graph

text: Theory

text: X.-S.

text: Liu

text: and

text: K.

text: Deng,

text: An

text: upper

text: bound

text: on

text: the

text: star

text: chromatic

text: index

text: of

text: graphs

text: with

text: J

text: Lanzhou

text: Univ

text: (Nat

text: Sci)

text: J.

text: Nešetřil

text: and

text: P.

text: Ossona

text: de

text: Mendez,

text: Colorings

text: and

text: homomorphisms

text: of

text: minor

text: closed

text: classes,

text: Algorithms

text: and

text: Combinatorics,

text: Vol.

text: Springer,

text: Berlin,

text: pp.

text: K.

text: Pradeep

text: and

text: V.

text: Vijayalakshmi,

text: Star

text: chromatic

text: index

text: of

text: subcubic

text: graphs,

text: Electron.

text: Notes

text: Discrete

text: Math.

text: V.

text: G.

text: Vizing,

text: On

text: an

text: estimate

text: of

text: the

text: chromatic

text: class

text: of

text: a

text: p-graph,

text: Diskret

text: Analiz

text: (in

text: Russian).


text: [6] John M. Hitchcock. Correspondence principles for eﬀective dimensions. Theory of Computing Systems, 38(5):559–571, 2005. [7] Ming Li and Paul M.B. Vit´anyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, third edition, 2008. [8] Jack H. Lutz. The dimensions of individual strings and sequences. Inf. Comput., 187(1):49–79, 2003. [9] Jack H. Lutz and Neil Lutz. Algorithmic information, plane Kakeya sets, and conditional dimension. Proceedings of the 34th International Sympo- sium on Theoretical Aspects of Computer Science, STACS 2017, Hannover, Germany, to appear. [10] Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM J. Comput., 38(3):1080–1112, 2008. [11] Neil Lutz and D. M. Stull. Bounding the dimension of points on a line. Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017, Bern, Switzerland, to appear. [12] Elvira Mayordomo. A Kolmogorov complexity characterization of construc- tive Hausdorﬀ dimension. Inf. Process. Lett., 84(1):1–3, 2002. [13] Jan Reimann. Eﬀectively closed classes of measures and randomness. An- nals of Pure and Applied Logic, 156(1), 2008. [14] Daniel Turetsky. Connectedness properties of dimension level sets. Theor. Comput. Sci., 412(29):3598–3603, 2011. [15] Linda Brown Westrick. Computability in Ordinal Ranks and Symbolic Dy- namics. PhD thesis, University of California, Berkeley, 2014. [16] Thomas Wolﬀ. Recent work connected with the Kakeya problem. Prospects in Mathematics, pages 129–162, 1999. 11

text: John

text: M.

text: Hitchcock.

text: Correspondence

text: principles

text: for

text: eﬀective

text: dimensions.

text: Theory

text: of

text: Computing

text: Systems,

text: Ming

text: Li

text: and

text: Paul

text: M.B.

text: Vit´anyi.

text: An

text: Introduction

text: to

text: Kolmogorov

text: Complexity

text: and

text: Its

text: Applications.

text: Springer,

text: third

text: edition,

text: Jack

text: H.

text: Lutz.

text: The

text: dimensions

text: of

text: individual

text: strings

text: and

text: sequences.

text: Inf.

text: Comput.,

text: Jack

text: H.

text: Lutz

text: and

text: Neil

text: Lutz.

text: Algorithmic

text: information,

text: plane

text: Kakeya

text: sets,

text: and

text: conditional

text: dimension.

text: Proceedings

text: of

text: the

text: International

text: Sympo-

text: sium

text: on

text: Theoretical

text: Aspects

text: of

text: Computer

text: Science,

text: STACS

text: Hannover,

text: Germany,

text: to

text: appear.

text: Jack

text: H.

text: Lutz

text: and

text: Elvira

text: Mayordomo.

text: Dimensions

text: of

text: points

text: in

text: self-similar

text: fractals.

text: SIAM

text: J.

text: Comput.,

text: Neil

text: Lutz

text: and

text: D.

text: M.

text: Stull.

text: Bounding

text: the

text: dimension

text: of

text: points

text: on

text: a

text: line.

text: Proceedings

text: of

text: the

text: Annual

text: Conference

text: on

text: Theory

text: and

text: Applications

text: of

text: Models

text: of

text: Computation,

text: TAMC

text: Bern,

text: Switzerland,

text: to

text: appear.

text: Elvira

text: Mayordomo.

text: A

text: Kolmogorov

text: complexity

text: characterization

text: of

text: construc-

text: tive

text: Hausdorﬀ

text: dimension.

text: Inf.

text: Process.

text: Lett.,

text: Jan

text: Reimann.

text: Eﬀectively

text: closed

text: classes

text: of

text: measures

text: and

text: randomness.

text: An-

text: nals

text: of

text: Pure

text: and

text: Applied

text: Logic,

text: Daniel

text: Turetsky.

text: Connectedness

text: properties

text: of

text: dimension

text: level

text: sets.

text: Theor.

text: Comput.

text: Sci.,

text: Linda

text: Brown

text: Westrick.

text: Computability

text: in

text: Ordinal

text: Ranks

text: and

text: Symbolic

text: Dy-

text: namics.

text: PhD

text: thesis,

text: University

text: of

text: California,

text: Berkeley,

text: Thomas

text: Wolﬀ.

text: Recent

text: work

text: connected

text: with

text: the

text: Kakeya

text: problem.

text: Prospects

text: in

text: Mathematics,

text: pages


text: ≤ Otherwise, when t r , by our construction of M and Lemma A.1, k ≥ (η + ε)r K(p , p ) k 1 2 ≥ K − (u, v) ≥ rk γ − K (u, v) O(log r ) . rk k Combining this with condition 3 in the lemma statement and simplifying yields − ≤ 2ε r t r + O(log r ) . k δ k k Therefore, by Lemma A.1, we have | ≤ − K (a, b, x u, v, x) 2(r t) + O(log r ) rk k k ≤ 4ε r + O(log r ) , (6) δ k k ∈ N for every t . Combining inequalities (4), (5) and (6) gives | ≤ | | K (a, b, x x, ax + b) K (u, v, x x, ax + b) + K (a, b, x u, v, x) rk rk rk ≤ | 4ε K (u, v, x x, ax + b) + r + O(log r ) rk δ k k (cid:18) (cid:19) ≤ 4ε (cid:96)(π ) + K(ε) + K(η) + r + O(log r ) 5 δ k k ≤ 4ε 2k K(ε) + K(η) + r + O(log r ) . δ k k A.3 Decreasing Complexity Using an Oracle ⊆ N ∈ N ∈ R ∈ Q ∩ Given an oracle D , r , z n, and η [0, dimD(z)], let AD(r, z, η) be the oracle guaranteed by applying Lemma A.3 relative to D. For ⊆ N (cid:104) (cid:105) ⊆ N oracles, A, B , let A, B be an oracle that combines A and B by interleaving. Note that we treat k as a constant for the purposes of asymptotic notation. ∈ R ∈ Q ∩ ∈ N ∈ N Lemma 7. Let z n, η [0, dim(z)], and k . For all r , . . . , r , 1 k there is an oracle D = D(r , . . . , r , z, η) such that 1 k ≤ { } 1. For every t r , KD(z) = min ηr , K (z) + O(log r ) 1 t 1 t k ≤ ≤ 2. For every 1 i k,(cid:88) i { − | } KrDi (z) = ηr1 + min η(rl rl−1), Krl,rl−1(z z) + O(log rk) . l=2 A4 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Otherwise,

text: when

text: t

text: r

text: by

text: our

text: construction

text: of

text: M

text: and

text: Lemma

text: k

text: (η

text: ε)r

text: K(p

text: p

text: k

text: K

text: (u,

text: v)

text: rk

text: γ

text: K

text: (u,

text: v)

text: O(log

text: r

text: rk

text: k

text: Combining

text: this

text: with

text: condition

text: in

text: the

text: lemma

text: statement

text: and

text: simplifying

text: yields

text: 2ε

text: r

text: t

text: r

text: O(log

text: r

text: k

text: δ

text: k

text: k

text: Therefore,

text: by

text: Lemma

text: we

text: have

label: equation

text: K

text: (a,

text: b,

text: x

text: u,

text: v,

text: x)

text: t)

text: O(log

text: r

text: rk

text: k

text: k

text: 4ε

text: r

text: O(log

text: r

text: δ

text: k

text: k

text: N

text: for

text: every

text: t

text: Combining

text: inequalities

text: and

text: gives

text: K

text: (a,

text: b,

text: x

text: x,

text: ax

text: b)

text: K

text: (u,

text: v,

text: x

text: x,

text: ax

text: b)

text: K

text: (a,

text: b,

text: x

text: u,

text: v,

text: x)

text: rk

text: rk

text: rk

text: 4ε

text: K

text: (u,

text: v,

text: x

text: x,

text: ax

text: b)

text: r

text: O(log

text: r

text: rk

text: δ

text: k

text: k

text: 4ε

text: K(ε)

text: K(η)

text: r

text: O(log

text: r

text: δ

text: k

text: k

text: 4ε

text: K(ε)

text: K(η)

text: r

text: O(log

text: r

text: δ

text: k

text: k

text: Decreasing

text: Complexity

text: Using

text: an

text: Oracle

text: N

text: N

text: R

text: Q

text: Given

text: an

text: oracle

text: D

text: r

text: z

text: n,

text: and

text: η

text: dimD(z)],

text: let

text: AD(r,

text: z,

text: η)

text: be

text: the

text: oracle

text: guaranteed

text: by

text: applying

text: Lemma

text: relative

text: to

text: D.

text: For

text: N

text: N

text: oracles,

text: A,

text: B

text: let

text: A,

text: B

text: be

text: an

text: oracle

text: that

text: combines

text: A

text: and

text: B

text: by

text: interleaving.

text: Note

text: that

text: we

text: treat

text: k

text: as

text: a

text: constant

text: for

text: the

text: purposes

text: of

text: asymptotic

text: notation.

text: R

text: Q

text: N

text: N

text: Lemma

text: Let

text: z

text: n,

text: η

text: dim(z)],

text: and

text: k

text: For

text: all

text: r

text: r

text: k

text: there

text: is

text: an

text: oracle

text: D

text: D(r

text: r

text: z,

text: η)

text: such

text: that

text: k

text: For

text: every

text: t

text: r

text: KD(z)

text: min

text: ηr

text: K

text: (z)

text: O(log

text: r

text: t

text: t

text: k

text: For

text: every

text: i

text: i

text: KrDi

text: (z)

text: min

text: η(rl

text: z)

text: O(log

text: rk)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: and Lemma A.3, KDj(z) =KDj−1(z) ri ri (cid:88) | − =KrDi−j−11(z) + KrDi,jr−i−1 1(z z) O(log rj) − i 1 { − | } =ηr1 + min η(rl rl−1), Krl,rl−1(z z) + O(log rj) l=2 (cid:88) | + Kri,ri−1(z z) + O(log rj−1 i { − | } =ηr1 + min η(rl rl−1), Krl,rl−1(z z) + O(log rj) . l=2 ≥ − If instead KDj−1(z) ηr , then KDj(z) = ηr O(log r ) by Lemma A.3, relative ri (cid:80)i ≥ ri i i | ≥ − to Dj−1. Since KrDij−1(z) ηri implies that Kri,ri−1(z z) η(ri ri−1), { − | } KrDij(z) = ηr1 + il=2 min η(rl rl−1), Krl,rl−1(z z) + O(log ri) ≤ ≤ Therefore property 2 holds for all 1 i k. To complete the proof we show that property 3 is satisﬁed for k = j. Let ∈ N ∈ R t and y m. By Lemma A.3, relativized to D − , and our induction j 1 hypothesis, Kz,Dj(y) = Kz,Dj−1(y) + O(log r ) t t j = Kz(y) + O(log r − ) + O(log r ) t j 1 j = Kz(y) + O(log r ) . t j ∈ N Thus, by mathematical induction, the lemma holds for all k . A.4 Proof of Second Main Theorem ∈ R ≥ ∈ Theorem 9. Let a, b such that dim(a, b) 1. Then for every s [1, 1] ∈ R ∈ − 2 there is a point x such that dim(x, ax + b) [3 + s 1 , s + 1]. 2 2s ∈ ∈ R Proof. Let s [1, 1] and y be random relative to (a, b). That is, there is 2∈ N ∈ N some constant c such that for all r , ≥ − Ka,b(y) r c. r { } Deﬁne sequence of nat(cid:26)ural numbers h ∈N in(cid:18)ductively as fol(cid:19)low(cid:27)s. Deﬁne h = j j 0 1. For every j > 0, deﬁne ≥ ≤ 1 h = min h 2hj−1 : K (a, b) dim(a, b) + h . j h j (cid:40) (cid:0)∈ N (cid:3) Note that h always exists. For every r , let j ∈ ∈ N 0 if r 1, 1 for some j x[r] = hj s y[r] otherwise A6 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: and

text: Lemma

text: KDj(z)

text: ri

text: ri

text: z)

text: O(log

text: rj)

text: i

text: min

text: η(rl

text: z)

text: O(log

text: rj)

text: z)

text: O(log

text: i

text: min

text: η(rl

text: z)

text: O(log

text: rj)

text: If

text: instead

text: ηr

text: then

text: KDj(z)

text: ηr

text: O(log

text: r

text: by

text: Lemma

text: relative

text: ri

text: ri

text: i

text: i

text: to

text: Since

text: ηri

text: implies

text: that

text: z)

text: η(ri

text: KrDij(z)

text: min

text: η(rl

text: z)

text: O(log

text: ri)

text: Therefore

text: property

text: holds

text: for

text: all

text: i

text: k.

text: To

text: complete

text: the

text: proof

text: we

text: show

text: that

text: property

text: is

text: satisﬁed

text: for

text: k

text: j.

text: Let

text: N

text: R

text: t

text: and

text: y

text: m.

text: By

text: Lemma

text: relativized

text: to

text: D

text: and

text: our

text: induction

text: j

text: hypothesis,

text: Kz,Dj(y)

text: O(log

text: r

text: t

text: t

text: j

text: Kz(y)

text: O(log

text: r

text: O(log

text: r

text: t

text: j

text: j

text: Kz(y)

text: O(log

text: r

text: t

text: j

text: N

text: Thus,

text: by

text: mathematical

text: induction,

text: the

text: lemma

text: holds

text: for

text: all

text: k

text: Proof

text: of

text: Second

text: Main

text: Theorem

text: R

text: Theorem

text: Let

text: a,

text: b

text: such

text: that

text: dim(a,

text: b)

text: Then

text: for

text: every

text: s

text: R

text: there

text: is

text: a

text: point

text: x

text: such

text: that

text: dim(x,

text: ax

text: b)

text: s

text: s

text: R

text: Proof.

text: Let

text: s

text: and

text: y

text: be

text: random

text: relative

text: to

text: (a,

text: b).

text: That

text: is,

text: there

text: is

text: 2∈

text: N

text: N

text: some

text: constant

text: c

text: such

text: that

text: for

text: all

text: r

text: Ka,b(y)

text: r

text: c.

text: r

text: Deﬁne

text: sequence

text: of

text: numbers

text: h

text: ∈N

text: as

text: Deﬁne

text: h

text: j

text: j

text: For

text: every

text: j

text: deﬁne

text: h

text: min

text: h

text: K

text: (a,

text: b)

text: dim(a,

text: b)

text: h

text: j

text: h

text: j

text: N

text: Note

text: that

text: h

text: always

text: exists.

text: For

text: every

text: r

text: let

text: j

text: N

text: if

text: r

text: for

text: some

text: j

text: x[r]

text: hj

text: s

text: y[r]

text: otherwise

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Intuitively, these dimensions measure the density of algorithmic information in the point x. Guided by the information-theoretic nature of these characteriza- tions, J. Lutz and N. Lutz [9] deﬁned the lower and upper conditional dimension ∈ R ∈ R of x m given y n as | | | K (x y) | K (x y) dim(x y) = lim inf r and Dim(x y) = lim sup r . r→∞ r r→∞ r 2.4 Relative Complexity and Dimensions By letting the underlying ﬁxed preﬁx-free Turing machine U be a universal oracle machine, we may relativize the deﬁnition in this section to an arbitrary or- ⊆ N | | acle set A . The deﬁnitions of KA(σ τ), KA(σ), KA(x), KA(x y), dimA(x), | | r r DimA(x) dimA(x y), and DimA(x y) are then all identical to their unrelativized versions, except that U is given oracle access to A. ∈ R We will frequently consider the complexity of a point x n relative to a ∈ R point y m, i.e., relative to a set A that encodes the binary expansion of y is y a standard way. We then write Ky(x) for KAy(x). J. Lutz and N. Lutz showed ≤ | r r that Ky(x) K (x y) + K(t) + O(1) [9]. r r,t 3 Background and Approach In this section we describe the basic ideas behind our investigation of dimen- sion spectra of lines. We brieﬂy discuss some of our earlier work on this subject, and we present two technical lemmas needed for the proof our main theorems. R The dimension of a point on a line in 2 has the following trivial bound. ∈ R ≤ Observation 2. For all a, b, x , dim(x, ax + b) dim(x, a, b). In this work, our goal is to ﬁnd values of x for which the approximate converse ≥ dim(x, ax + b) dima,b(x) + dim(a, b) (1) holds. There exist oracles, at least, relative to which (1) does not always hold. This follows from the point-to-set principle of J. Lutz and N. Lutz [9] and the existence of Furstenberg sets with parameter α and Hausdorﬀ dimension less than 1 + α (attributed by Wolﬀ [16] to Furstenberg and Katznelson “in all probability”). The argument is simple and very similar to our proof in [11] of a lower bound on the dimension of generalized Furstenberg sets. ∈ Speciﬁcally, for every s [0, 1], we want to ﬁnd an x of eﬀective Hausdorﬀ dimension s such that (1) holds. Note that equality in Observation 2 implies (1). (cid:18) (cid:54) (cid:19) Observation 3. Suppose ax + b = ux + v and u = a. Then − ≥ ≥ b v dim(u, v) dima,b(u, v) dima,b − = dima,b(x) . u a 4 ##LTLine## ##LTLine## ##LTLine##

text: Intuitively,

text: these

text: dimensions

text: measure

text: the

text: density

text: of

text: algorithmic

text: information

text: in

text: the

text: point

text: x.

text: Guided

text: by

text: the

text: information-theoretic

text: nature

text: of

text: these

text: characteriza-

text: tions,

text: J.

text: Lutz

text: and

text: N.

text: Lutz

text: deﬁned

text: the

text: lower

text: and

text: upper

text: conditional

text: dimension

text: R

text: R

text: of

text: x

text: m

text: given

text: y

text: n

text: as

text: K

text: (x

text: y)

text: K

text: (x

text: y)

text: dim(x

text: y)

text: lim

text: inf

text: r

text: and

text: Dim(x

text: y)

text: lim

text: sup

text: r

text: r→∞

text: r

text: r→∞

text: r

label: section

text: Relative

text: Complexity

text: and

text: Dimensions

text: By

text: letting

text: the

text: underlying

text: ﬁxed

text: preﬁx-free

text: Turing

text: machine

text: U

text: be

text: a

text: universal

text: oracle

text: machine,

text: we

text: may

text: relativize

text: the

text: deﬁnition

text: in

text: this

text: section

text: to

text: an

text: arbitrary

text: or-

text: N

text: acle

text: set

text: A

text: The

text: deﬁnitions

text: of

text: KA(σ

text: τ),

text: KA(σ),

text: KA(x),

text: KA(x

text: y),

text: dimA(x),

text: r

text: r

text: DimA(x)

text: dimA(x

text: y),

text: and

text: DimA(x

text: y)

text: are

text: then

text: all

text: identical

text: to

text: their

text: unrelativized

text: versions,

text: except

text: that

text: U

text: is

text: given

text: oracle

text: access

text: to

text: A.

text: R

text: We

text: will

text: frequently

text: consider

text: the

text: complexity

text: of

text: a

text: point

text: x

text: n

text: relative

text: to

text: a

text: R

text: point

text: y

text: m,

text: i.e.,

text: relative

text: to

text: a

text: set

text: A

text: that

text: encodes

text: the

text: binary

text: expansion

text: of

text: y

text: is

text: y

text: a

text: standard

text: way.

text: We

text: then

text: write

text: Ky(x)

text: for

text: KAy(x).

text: J.

text: Lutz

text: and

text: N.

text: Lutz

text: showed

text: r

text: r

text: that

text: Ky(x)

text: K

text: (x

text: y)

text: K(t)

text: r

text: r,t

text: Background

text: and

text: Approach

text: In

text: this

text: section

text: we

text: describe

text: the

text: basic

text: ideas

text: behind

text: our

text: investigation

text: of

text: dimen-

text: sion

text: spectra

text: of

text: lines.

text: We

text: brieﬂy

text: discuss

text: some

text: of

text: our

text: earlier

text: work

text: on

text: this

text: subject,

text: and

text: we

text: present

text: two

text: technical

text: lemmas

text: needed

text: for

text: the

text: proof

text: our

text: main

text: theorems.

text: R

text: The

text: dimension

text: of

text: a

text: point

text: on

text: a

text: line

text: in

text: has

text: the

text: following

text: trivial

text: bound.

text: R

text: Observation

text: For

text: all

text: a,

text: b,

text: x

text: dim(x,

text: ax

text: b)

text: dim(x,

text: a,

text: b).

text: In

text: this

text: work,

text: our

text: goal

text: is

text: to

text: ﬁnd

text: values

text: of

text: x

text: for

text: which

text: the

text: approximate

text: converse

text: dim(x,

text: ax

text: b)

text: dima,b(x)

text: dim(a,

text: b)

text: holds.

text: There

text: exist

text: oracles,

text: at

text: least,

text: relative

text: to

text: which

text: does

text: not

text: always

text: hold.

text: This

text: follows

text: from

text: the

text: point-to-set

text: principle

text: of

text: J.

text: Lutz

text: and

text: N.

text: Lutz

text: and

text: the

text: existence

text: of

text: Furstenberg

text: sets

text: with

text: parameter

text: α

text: and

text: Hausdorﬀ

text: dimension

text: less

text: than

text: α

text: (attributed

text: by

text: Wolﬀ

text: to

text: Furstenberg

text: and

text: Katznelson

text: “in

text: all

text: probability”).

text: The

text: argument

text: is

text: simple

text: and

text: very

text: similar

text: to

text: our

text: proof

text: in

text: of

text: a

text: lower

text: bound

text: on

text: the

text: dimension

text: of

text: generalized

text: Furstenberg

text: sets.

text: Speciﬁcally,

text: for

text: every

text: s

text: we

text: want

text: to

text: ﬁnd

text: an

text: x

text: of

text: eﬀective

text: Hausdorﬀ

text: dimension

text: s

text: such

text: that

text: holds.

text: Note

text: that

text: equality

text: in

text: Observation

text: implies

text: Observation

text: Suppose

text: ax

text: b

text: ux

text: v

text: and

text: u

text: a.

text: Then

text: b

text: v

text: dim(u,

text: v)

text: dima,b(u,

text: v)

text: dima,b

text: dima,b(x)

text: u

text: a

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 2. Figure 1 (left) shows the Fermi 95% error circle super- and Halpern & Thorstensen (2015). The CCD readout posed on the XMM–Newton pn image of 2015 December was windowed and binned to reduce dead-time. Expo- − 2. In addition to 1RXS J083842.1 282723 (source “a”), sure times were 10 s or 20 s, with 3 s dead-time using there are two fainter sources inside the error circle that Templeton, and 5 s exposures with 12 ms dead-time using we investigated, labeled “b” and “c”. The MOS small the Andor. A log of the observations is given in Table 1. window only included source “a”, but all three sources The 1.3m Templeton images (Figure 1, right) covered have optical counterparts in the OM images. all three X-ray sources, while the Andor and 2.4m Tem- − − We obtained another X-ray observation of 1RXS J083842.1 p28le2t7o2n3 images only included 1RXS J083842.1 282723. using Chandra ACIS on 2016 July 7 for an exposure time Optical positions for the three sources, measured from a of 30 ks (ObsID 17769). The S3 CCD only was operated 1.3m image using USNO B1.0 catalog stars for the as- in continuous clocking (CC) mode to avoid pileup of the trometric solution, are given in Table 2. − − bright source 1RXS J083842.1 282723. This gives time We obtained 59 spectra of 1RXS J083842.1 282723 resolution of 2.85 ms, but sacriﬁces one spatial dimen- during two observing runs, in 2016 January and Febru- − sion. Only 1RXS J083842.1 282723 is bright enough to ary, using the 2.4m telescope with the modular spec- × study in CC mode. trograph and a thinned, back-illuminated 2048 2048 We obtained several hours of time-series optical pho- pixel SITe CCD detector. Our spectra covered 4210– − tometry of the ﬁeld using the MDM Observatory 1.3m 7500 ˚A, with 2.0 ˚A pixel 1 and a FWHM resolution of ≈ and 2.4m telescopes om Kitt Peak during three observing 3.5 ˚A. The observing, reduction, and analysis protocols runs in 2014, ×2015, and 2016. The detectors used were ei- were practically identical to those used in Thorstensen ther the 1024 1024 pixel thinned, back-illuminated SITe & Halpern (2013) and Halpern & Thorstensen (2015). CCD “Templeton,” or a thermoelectrically cooled Andor A log of the spectroscopic observations is given in Ta- Ikon DU-937 N CCD camera. The detectors, observing ble 3. Finally, we obtained one identiﬁcation spectrum paPrraempreinttertysp,easnetdusdiniﬀgeLArTeEnXtiastlypleheomtuolmateeatprjyvt.e1c2h/1n6i/q1u1es were of source “c” using the Ohio State Multi-Object Spec- the same as described in Thorstensen & Halpern (2013) trograph (OSMOS) on the 2.4m. Jules P. Halpern1, Slavko Bogdanov1, and John R. Thorstensen2 (Received 2016 November 8; Accepted 2017 January 13) Subject headings: cataclysmic variables — gamma rays: stars — pulsars: general — X-rays: individual − − − (1RXS J083842.1 282723, XMMU J083850.38 282756.8, XMMU J083842.85 282831.8) 1 Columbia Astrophysics Laboratory, Columbia Univer- sity, 550 West 120th Street, New York, NY 10027-6601; jules@astro.columbia.edu 2 Department of Physics and Astronomy, 6127 Wilder Labo- ratory, Dartmouth College, Hanover, NH 03755-3528

text: Figure

text: (left)

text: shows

text: the

text: Fermi

text: error

text: circle

text: super-

text: and

text: Halpern

text: Thorstensen

text: The

text: CCD

text: readout

text: posed

text: on

text: the

text: XMM–Newton

text: pn

text: image

text: of

text: December

text: was

text: windowed

text: and

text: binned

text: to

text: reduce

text: dead-time.

text: Expo-

text: In

text: addition

text: to

text: (source

text: “a”),

text: sure

text: times

text: were

text: s

text: or

text: s,

text: with

text: s

text: dead-time

text: using

text: there

text: are

text: two

text: fainter

text: sources

text: inside

text: the

text: error

text: circle

text: that

text: Templeton,

text: and

text: s

text: exposures

text: with

text: ms

text: dead-time

text: using

text: we

text: investigated,

text: labeled

text: “b”

text: and

text: “c”.

text: The

text: MOS

text: small

text: the

text: Andor.

text: A

text: log

text: of

text: the

text: observations

text: is

text: given

text: in

text: Table

text: window

text: only

text: included

text: source

text: “a”,

text: but

text: all

text: three

text: sources

text: The

text: Templeton

text: images

text: (Figure

text: right)

text: covered

text: have

text: optical

text: counterparts

text: in

text: the

text: OM

text: images.

text: all

text: three

text: X-ray

text: sources,

text: while

text: the

text: Andor

text: and

text: Tem-

text: We

text: obtained

text: another

text: X-ray

text: observation

text: of

text: images

text: only

text: included

text: using

text: Chandra

text: ACIS

text: on

text: July

text: for

text: an

text: exposure

text: time

text: Optical

text: positions

text: for

text: the

text: three

text: sources,

text: measured

text: from

text: a

text: of

text: ks

text: (ObsID

text: The

text: CCD

text: only

text: was

text: operated

text: image

text: using

text: USNO

text: catalog

text: stars

text: for

text: the

text: as-

text: in

text: continuous

text: clocking

text: (CC)

text: mode

text: to

text: avoid

text: pileup

text: of

text: the

text: trometric

text: solution,

text: are

text: given

text: in

text: Table

text: bright

text: source

text: This

text: gives

text: time

text: We

text: obtained

text: spectra

text: of

text: resolution

text: of

text: ms,

text: but

text: sacriﬁces

text: one

text: spatial

text: dimen-

text: during

text: two

text: observing

text: runs,

text: in

text: January

text: and

text: Febru-

text: sion.

text: Only

text: is

text: bright

text: enough

text: to

text: ary,

text: using

text: the

text: telescope

text: with

text: the

text: modular

text: spec-

text: study

text: in

text: CC

text: mode.

text: trograph

text: and

text: a

text: thinned,

text: back-illuminated

text: We

text: obtained

text: several

text: hours

text: of

text: time-series

text: optical

text: pho-

text: pixel

text: SITe

text: CCD

text: detector.

text: Our

text: spectra

text: covered

text: tometry

text: of

text: the

text: ﬁeld

text: using

text: the

text: MDM

text: Observatory

text: ˚A,

text: with

text: ˚A

text: pixel

text: and

text: a

text: FWHM

text: resolution

text: of

text: and

text: telescopes

text: om

text: Kitt

text: Peak

text: during

text: three

text: observing

text: ˚A.

text: The

text: observing,

text: reduction,

text: and

text: analysis

text: protocols

text: runs

text: in

text: and

text: The

text: detectors

text: used

text: were

text: ei-

text: were

text: practically

text: identical

text: to

text: those

text: used

text: in

text: Thorstensen

text: ther

text: the

text: pixel

text: thinned,

text: back-illuminated

text: SITe

text: Halpern

text: and

text: Halpern

text: Thorstensen

text: CCD

text: “Templeton,”

text: or

text: a

text: thermoelectrically

text: cooled

text: Andor

text: A

text: log

text: of

text: the

text: spectroscopic

text: observations

text: is

text: given

text: in

text: Ta-

text: Ikon

text: N

text: CCD

text: camera.

text: The

text: detectors,

text: observing

text: ble

text: Finally,

text: we

text: obtained

text: one

text: identiﬁcation

text: spectrum

text: were

text: of

text: source

text: “c”

text: using

text: the

text: Ohio

text: State

text: Multi-Object

text: Spec-

text: the

text: same

text: as

text: described

text: in

text: Thorstensen

text: Halpern

text: trograph

text: (OSMOS)

text: on

text: the

text: Jules

text: P.

text: Slavko

text: and

text: John

text: R.

text: (Received

text: November

text: Accepted

text: January

text: Subject

text: headings:

text: cataclysmic

text: variables

text: gamma

text: rays:

text: stars

text: pulsars:

text: general

text: X-rays:

text: individual

text: XMMU

text: XMMU

text: Columbia

text: Astrophysics

text: Laboratory,

text: Columbia

text: Univer-

text: sity,

text: West

text: Street,

text: New

text: York,

text: NY

text: jules@astro.columbia.edu

text: Department

text: of

text: Physics

text: and

text: Astronomy,

text: Wilder

text: Labo-

text: ratory,

text: Dartmouth

text: College,

text: Hanover,

text: NH