text:
# The Lazy Bureaucrat Scheduling Problem Appears in preliminary form in Proceedings of the Workshop on Discrete Algorithms (WADS), Vancouver, BC, Canada, Aug 11–14, 1999, pages 122–133 [1].

## 1 Introduction

Scheduling problems have been studied extensively from the point of view of the objectives of the enterprise that stands to gain from the completion of a set of jobs. We take a new look at the problem from the point of view of the workers who perform the tasks that earn the company its profits. In fact, it is natural to expect that some employees may lack the motivation to perform at their peak levels of efficiency, either because they have no stake in the company’s profits or because they are simply lazy.

The following example illustrates the situation facing a “typical” office worker, who may be one small cog in a large bureaucracy:

> Example. It is 3:00 p.m., and Dilbert goes home at 5:00 p.m. Dilbert has two tasks that have been given to him: one requires 10 minutes, the other requires an hour. If there is a task in his “in-box,” Dilbert must work on it, or risk getting fired. However, if he has multiple tasks, Dilbert has the freedom to choose which one to do first. He also knows that at 3:15, another task will appear — a 45-minute personnel meeting. If Dilbert begins the 10-minute task first, he will be free to attend the personnel meeting at 3:15 and then work on the hour-long task from 4:00 until 5:00. On the other hand, if Dilbert is part way into the hour-long job at 3:15, he may be excused from the meeting. After finishing the 10-minute job by 4:10, he will have 50 minutes to twiddle his thumbs, iron his tie, or enjoy engaging in other mindless trivia. Naturally, Dilbert prefers this latter option.

An historical example of a situation where it proved crucial to schedule tasks inefficiently is documented in the book/movie Schindler’s List . It was essential for the workers and management of Schindler’s factory to appear to be busy at all times in order for the factory to stay in operation, but they simultaneously sought to minimize their contribution to the German war effort.

These examples illustrate a general and natural type of scheduling problem, which we term the “Lazy Bureaucrat Problem” (LBP); the goal of the LBP is to schedule jobs as inefficiently (in some sense) as possible. There exists a vast literature on scheduling; see e.g., some of the recent surveys . The LBP studies these traditional problems “in reverse.” Several other combinatorial optimization problems have also been studied in reverse, leading, e.g., to maximum TSP , maximum cut , and longest path ; such inquiries often lead to a better understanding of the structure and algorithmic complexity of the original optimization problem.

### 1.1 The Model

In this paper we schedule a set of jobs $`1\mathrm{}n`$ having processing times (lengths) $`t_1\mathrm{}t_n`$ respectively. Job $`i`$ arrives at time $`a_i`$ and has its deadline at time $`d_i`$. We assume throughout this paper that $`t_i`$, $`a_i`$, and $`d_i`$ have nonnegative integral values. The jobs have hard deadlines, meaning that each job $`i`$ can only be executed during its allowed interval $`I_i=[a_i,d_i]`$; we also call $`I_i`$ the job’s window. We let $`c_i=d_it_i`$ denote the critical time of job $`i`$; job $`i`$ must be started by time $`c_i`$ if there is any chance of completing it on time.

The jobs are executed on a single processor, the (lazy) bureaucrat. The bureaucrat executes only one job at a time.

#### 1.1.1 Busy Requirement

The bureaucrat chooses a subset of jobs to execute. Since the bureaucrat’s goal is to minimize his effort, he would prefer to remain idle all the time and to leave all the jobs unexecuted. However, this scenario is forbidden by what we call the busy requirement, which stipulates that the bureaucrat work on an executable job, if any executable jobs exist. A job is executable if the constraints of the LBP allow the job to be run. Thus, in the nonpreemptive setting a job $`j`$ is executable as long as it begun during the interval $`[a_j,c_j]`$, at which point it is run to completion. In the preemptive setting the constraints that govern whether or not a job can be executed are more complicated; see Section 3.

#### 1.1.2 Objective Functions

In traditional scheduling problems, if it is impossible to complete the set of all jobs by their deadlines, one typically optimizes according to some objective, e.g., to maximize a weighted sum of on-time jobs, to minimize the maximum lateness of the jobs, or to minimize the number of late jobs. For the LBP we consider three different objective functions, which naturally arise from the bureaucrat’s goal of inefficiency:

1. Minimize the total amount of time spent working — This objective naturally appeals to a “lazy” bureaucrat.
2. Minimize the weighted sum of completed jobs — In this paper we usually assume that the weight of job $`i`$ is its length, $`t_i`$; however, other weights (e.g., unit weights) are also of interest. This objective appeals to a “spiteful” bureaucrat whose goal it is to minimize the fees that the company collects on the basis of his labors, assuming that the fee (in proportion to the task length, or a fixed fee per task) is collected only for those tasks that are actually completed.
3. Minimize the makespan, the maximum completion time of the jobs — This objective appeals to an “impatient” bureaucrat, whose goal it is to go home as early as possible, at the completion of the last job he is able to complete. He cares about the number of hours spent at the office, not the number of hours spent doing work (productive or otherwise) at the office.

Note that, in contrast with standard scheduling problems on one processor, the makespan in the LBP varies; it is a function of which jobs have passed their deadlines and can no longer be executed.

#### 1.1.3 Additional Parameters of the Model

As with most scheduling problems, additional parameters of the model must be set. For example, we must explicitly allow or forbid preemption of jobs. When a job is preempted, it is interrupted and may be resumed later at no additional cost. If we forbid preemption, then once a job is begun, it must be completed without interruptions.

We must also specify whether scheduling occurs on-line or off-line. A scheduling algorithm is off-line if all the jobs are known to the scheduler at the outset; it is on-line if the jobs are known to the scheduler only as they arrive. In this paper we restrict ourselves to off-line scheduling; we leave the on-line case as an open problem.

### 1.2 Our Results

In this paper, we introduce the Lazy Bureaucrat Problem and develop algorithms and hardness results for several versions of the LBP. From these results, we derive some general characteristics of this new class of scheduling problems and describe (1) situations in which traditional scheduling algorithms extend to the LBP and (2) situations in which these algorithms no longer apply.

#### 1.2.1 No Preemption

We prove that the LBP is NP-complete, as is often the case for traditional scheduling problems. Thus, we focus on special cases to study exact algorithms. When all jobs have unit size, optimal schedules can be found in polynomial time. The following three cases have pseudo-polynomial algorithms: (1) when each job $`i`$’s interval $`I_i`$ is less than twice the processing time of job $`i`$; (2) when the ratios of interval length to job length and longest job to shortest job are both bounded; and (3) when all jobs arrive in the system at the same time. These last scheduling problems are solved using dynamic programming both for Lazy Bureaucrat and traditional metrics. Thus, in these settings, the Lazy Bureaucrat metrics and traditional metrics are solved using similar techniques.

From the point of view of approximation, however, the standard and Lazy Bureaucrat metrics behave differently. Standard metrics typically allow polynomial-time algorithms having good approximation ratios, whereas we show that the Lazy Bureaucrat metrics are difficult to approximate. This hardness derives more from the busy requirement and less from the particular metric in question, that is the busy requirement appears to render the problem substantially more difficult. (Ironically, even in standard optimization problems, the management often imposes this requirement because it intuitively appears desirable.)

#### 1.2.2 Preemption

The busy requirement dictates that the worker must stay busy while work is in the system. If the model allows preemption we must specify under what conditions a job can be interrupted or resumed. We distinguish three versions of the preemption rules, which we list from most permissive to most restrictive. In particular, workers are constrained to execute the following jobs:

(I) any job that has arrived and is before its deadline,

(II) any job that has arrived and for which there is still time to complete it before its deadline, or

(III) any job that has arrived, but with the constraint that if it is started, it must eventually be completed.

We consider all three metrics and all three versions of preemption. We show that, for all three metrics, version I is polynomially solvable, and version III is NP-complete. Many of the hardness results for no preemption carry over to version III.

Our main results are for version II. We show that the general problem is NP-complete. Then, we focus on minimizing the makespan in two complementary special cases:

1. All jobs have a common arrival time and arbitrary deadlines.
2. All jobs have a common deadline and arbitrary arrival times.

We show that the first problem is NP-complete, whereas the second problem can be solved in polynomial time.

These last results illustrate a curious feature of the LBP. One can convert one special case into the other by reversing the direction of time. In the LBP, unlike many scheduling settings, this reversing of time changes the complexity of the problem.

### 1.3 Related Work on the LBP

Recently Hepner and Stein  published a pseudo-polynomial-time algorithm for minimizing the makespan subject to preemption constraint II, thus resolving an open problem from an earlier version of this paper . They also extend the LBP to the parallel setting, in which there are multiple bureaucrats.

## 2 LBP: No Preemption

In this section, we assume that no job can be preempted: if a job is started, then it is performed without interruption until it completes. We show that the Lazy Bureaucrat Problem (LBP) without preemption is strongly NP-complete and is not approximable to within any factor for the three metrics we consider. These hardness results distinguish our problem from traditional scheduling metrics, which can be approximated in polynomial time, as proved in . We show, however, that several special cases of the problem have pseudo-polynomial-time algorithms, using applications of dynamic programming.

### 2.1 Hardness Results

We begin by describing the relationship between the three different objective functions from Section 2.1 in the case of no preemption.

The problem of minimizing the total work (objective function 1) is a special case of the problem of minimizing the weighted sum of completed jobs (objective function 2), because without preemption every job that is executed must be completed. (The weights become the job lengths.) Furthermore, if all jobs have the same arrival time, say time zero, then the two objectives minimizing the total amount of time spent working and minimizing the makespan (go home early) are equivalent (objective functions 1 and 3), since no feasible schedule will have any gaps. Our first hardness theorem applies therefore to all three objective functions from Section 2.1.

###### Theorem 1

The Lazy Bureaucrat Problem with no preemption is (weakly) NP-complete for objective functions (1)-(3), and is not approximable to within any fixed factor, even when all arrival times are the same.

Proof: We use a reduction from the Subset Sum problem : Given a set of integers $`S=\{x_1,x_2,\mathrm{},x_n\}`$ and a target integer $`T`$, does there exist a subset $`S^{}S`$, such that $`_{x_iS^{}}x_i=T`$?

We construct an instance of the LBP having $`n+1`$ jobs, each having release time zero ($`a_i=0`$ for all $`i`$). For $`i=1\mathrm{},n`$, job $`i`$ has processing time $`t_i=x_i`$ and deadline $`d_i=T`$. Job $`n+1`$ has processing time $`t_{n+1}=1+_{x_iS}x_i`$ and deadline $`d_{n+1}=T+t_{n+1}1`$; thus, job $`n+1`$ can be started at time $`T1`$ or earlier. Because job $`n+1`$ is so long, the bureaucrat wants to avoid executing it, but can do so if and only if he selects a subset of jobs from $`\{1,\mathrm{},n\}`$ to execute whose lengths sum to exactly $`T`$. In summary, the large job $`n+1`$ is executed if and only if the subset problem is solved exactly and executing the long job leads to a schedule whose makespan (i.e., total work executed) is not within any fixed factor of the optimal solution. $`\mathrm{}`$

We now show that the LBP with no preemption is strongly NP-complete. As we will show in Section 2.2, the LBP from Theorem 1 when all arrival times are equal, has a pseudo-polynomial-time algorithm. However, if arrival times and deadlines are arbitrary integers, the problem becomes strongly NP-complete. Thus, the following theorem subsumes Theorem 1 when arrival times and deadlines our unconstrained, whereas Theorem 1 is more generally applicable.

###### Theorem 2

The Lazy Bureaucrat Problem with no preemption is strongly NP-complete for objective functions (1)–(3), and is not approximable to within any fixed factor.

Proof: Clearly the problem is in NP, since any solution can be represented by an ordered list of jobs, given their arrival times. To show hardness, we use a reduction from the 3-Partition problem : Given a set $`S=\{x_1,\mathrm{},x_{3m}\}`$ of $`3m`$ positive integers and a positive integer bound $`B`$ such that $`B/4<x_i<B/2`$, for $`i=1,\mathrm{},3m`$ and $`_ix_i=mB`$, does there exist a partitioning of $`S`$ into $`m`$ disjoint sets, $`S_1,\mathrm{},S_m`$, such that for $`i=1,\mathrm{},m`$, $`_{x_jS_i}x_j=B`$? (Note that, by the assumption that $`B/4<x_i<B/2`$, each set $`S_i`$ must contain exactly 3 elements.)

Objective function (1) is a special case of objective function (2) because without preemption, any job that is begun must be completed. Furthermore, hard instances will be designed so that there are no gaps, ensuring that the optimal solution for objective function (1) is also the optimal solution for objective function (3).

We construct an instance of the LBP containing three classes of jobs:

* Element jobs — We define one “element job” corresponding to each element $`x_iS`$, having arrival time $`0`$, deadline $`d_i=(m1)+mB`$, and processing time $`x_i`$.
* Unit jobs — We define $`m1`$ “unit” jobs, each of length $`1`$. The $`i`$-th unit job (for $`i=1,\mathrm{},m1`$) has arrival time $`i(B+1)1`$ and deadline $`i(B+1)`$. Note that for these unit-length jobs we have $`d_ja_j=1`$; thus, these jobs must be processed immediately upon their arrival, or not at all.
* Large job — We define one “large” job of length $`L>(m1)+mB`$, arrival time $`0`$, and deadline $`L+(m2)+mB`$. Note that in order to complete this job, it must be started at time $`(m2)+mB`$ or before.

As in the proof of Theorem 1, the lazy bureaucrat wants to avoid executing the long job, but can do so if and only if all other jobs are actually executed. Otherwise, there will be a time when the large job is the only job in the system and the lazy bureaucrat will be forced to execute it. Thus, the unit jobs must be done immediately upon their arrival, and the element jobs must fit in the intervals between the unit jobs. Each such interval between consecutive unit jobs is of length exactly $`B`$. Refer to Figure 4. In summary, the long job is not processed if and only if all of the element and unit jobs can be processed before their deadlines, which happens if and only if the corresponding instance of 3-Partition is a “yes” instance. Note that since $`L`$ can be as large as we want, this also implies that no polynomial-time approximation algorithm with any fixed approximation bound can exist, unless P=NP. $`\mathrm{}`$

### 2.2 Algorithms for Special Cases

#### 2.2.1 Unit-Length Jobs

Consider the special case of the LBP in which all jobs have unit processing times. (Recall that all inputs are assumed to be integral.) The Latest Due Date (LDD) scheduling policy selects the job in the system having the latest deadline. Note that this policy in nonpreemptive for unit-length jobs, since all jobs have integral arrival times.

###### Theorem 3

Consider the Latest Deadline First scheduling policy when jobs have unit lengths and all inputs are integral. The LDD scheduling policy minimizes the amount of executed work.

Proof: Assume by contradiction that no optimal schedule is LDD. We use an exchange argument. Consider an optimal (non-LDD) schedule that has the fewest pairs of jobs executed in non-LDD order. The schedule must have two neighboring jobs $`i,j`$ such that $`i<j`$ in the schedule but $`D_i<D_j`$, and $`j`$ is in the system when $`i`$ starts its execution. Consider the first such pair of jobs. There are two cases:

(1) The new schedule with $`i`$ and $`j`$ switched, is feasible. It executes no more work than the optimal schedules, and is therefore also optimal.

(2) The schedule with $`i`$ and $`j`$ switched is not feasible. This happens if $`i`$’s deadline has passed. If no job is in the system to replace $`i`$, then we obtain a better schedule than the optimal schedule and reach a contradiction. Otherwise, we replace $`i`$ with the other job and repeat the switching process.

We obtain a schedule executing no more work than an optimal schedule, but with fewer pairs of jobs in non-LDD order, a contradiction. $`\mathrm{}`$

#### 2.2.2 Narrow Windows

Consider now the version in which jobs are large in comparison with their intervals, that is, the intervals are “narrow.” Let $`R`$ be a bound on the ratio of window length to job length; i.e., for each job $`i`$, $`d_ia_i<Rt_i`$. We show that a pseudo-polynomial algorithm exists for the case of sufficiently narrow windows, that is, when $`R2`$.

###### Lemma 4

Assume that for each job $`i`$, $`d_ia_i<2t_i`$. Then, if job $`i`$ can be scheduled before job $`j`$, then job $`j`$ cannot be scheduled before job $`i`$.

Proof: We rewrite the assumption: for each $`i`$, $`d_it_i<t_i+a_i`$. The fact that job $`i`$ can be scheduled before job $`j`$ is equivalent to the statement that $`a_i+t_id_jt_j`$, since the earliest that job $`i`$ can be completed is at time $`a_i+t_i`$ and the latest that job $`j`$ can be started is at time $`d_jt_j`$. Combining these inequalities, we obtain

$$a_j+t_j>d_jt_ja_i+t_i>d_it_i,$$

which implies that job $`j`$ cannot be scheduled before job $`i`$. $`\mathrm{}`$

###### Corollary 5

Under the assumption that $`d_ia_i<2t_i`$ for each $`i`$, the ordering of any subset of jobs in a schedule is uniquely determined.

###### Theorem 6

Suppose that for each job $`i`$, $`d_ia_i<2t_i`$. Let $`K=\mathrm{max}_id_i`$. Consider the problem of minimizing objective functions (1)-(3) from Section 1.1, in the nonpreemptive setting. Then the LBP can be solved in $`O(nK\mathrm{max}(n,K))`$ time.

Proof: We use dynamic programming to find the shortest path in a directed acyclic graph (DAG). There are $`O(nK^2)`$ states the system can enter. Let $`(i,j,\tau )`$ denote the state of the system when the processor begins executing the $`j`$-th unit of work of job $`i`$ at time $`\tau `$. Thus, $`i=1,\mathrm{},n`$, $`j=1,\mathrm{},t_i`$, and $`\tau =0,\mathrm{},K`$. Transitions from state to state are defined according to the following rules:

1. No preemption: once a job is begun, it must be completed without interruptions.
2. When a job is completed at time $`\tau `$, another job must begin immediately if one exists in the system. (By Lemma 4, we know this job has not yet been executed.) Otherwise, the system is idle and begins executing a job as soon as one arrives.
3. State $`(i,t_i,\tau )`$ is an end state if and only if when job $`i`$ completes at time $`\tau `$, no jobs can be executed subsequently.
4. The start state has transitions to the jobs $`(i,1,0)`$ that arrive first.

The goal of the dynamic program is to find the length of a shortest path from the start state to an end state. Depending on how we assign weights to the edges we can force our algorithm to minimize all three metrics from Section 1.1. To complete the time analysis, note that only $`nK`$ of the $`nK^2`$ states have more than constant outdegree, and these states each have outdegree bounded by $`n`$. $`\mathrm{}`$

For $`R>2`$ we know of no efficient algorithm without additional conditions. Let $`W`$ be a bound on the ratio of longest window to shortest window, and let $`\mathrm{\Delta }`$ be a bound on the ratio of the longest job to the shortest job. Note that bounds on $`R`$ and $`\mathrm{\Delta }`$ imply a bound on $`W`$, and bounds on $`R`$ and $`W`$ imply a bound on $`\mathrm{\Delta }`$. However, a bound on $`\mathrm{\Delta }`$ alone is not sufficient for a pseudo-polynomial-time algorithm.

###### Theorem 7

Even with a bound on the ratio $`\mathrm{\Delta }`$, the LBP with no preemption is strongly NP-complete for objective functions (1)-(3). It cannot be approximated to within a factor of $`\mathrm{\Delta }\epsilon `$, for any $`\epsilon >0`$, unless P=NP.

Proof: Modify the reduction from 3-partition of Theorem 2, by changing all the fixed “unit” jobs to have length $`B/3`$, and adjust the arrival times and deadlines accordingly.

Instead of one very long job as in the proof from Theorem 2, we create a sequence of bounded-length jobs that serve the same purpose. One unit before the deadline of the “element” jobs (see Theorem 2) a sequence of longer jobs $`\mathrm{}_1,\mathrm{},\mathrm{}_m`$ arrives. Each job $`\mathrm{}_i`$ entirely fills its window and so can only be executed directly when it arrives. Job $`\mathrm{}_{i+1}`$ arrives at the deadline of job $`\mathrm{}_i`$. In addition, a sequence of shorter jobs $`s_1,\mathrm{},s_m`$ arrives, where each shorter job $`s_i`$ also entirely fills its window and can only be executed when it arrives. Shorter job $`s_i`$ overlaps $`\mathrm{}_i`$ and $`\mathrm{}_{i+1}`$; it arrives one unit before the deadline of job $`\mathrm{}_i`$. Jobs $`s_i`$ have length $`B/4`$ and jobs $`\mathrm{}_i`$ have length $`\mathrm{\Delta }B/4`$. Thus, if all the jobs comprising the $`3`$-partition problem can be executed, jobs $`\mathrm{}_1,\mathrm{},\mathrm{}_m`$ will be avoided by executing jobs $`s_1,\mathrm{},s_m`$. Otherwise, jobs $`\mathrm{}_1,\mathrm{},\mathrm{}_m`$ must be executed. The index of $`m`$ can be adjusted to any $`\epsilon `$. $`\mathrm{}`$

Bounds on both $`\mathrm{\Delta }`$ and $`R`$ are sufficient to yield a pseudo-polynomial algorithm:

###### Theorem 8

Let $`K=\mathrm{max}_id_i`$. Given bounds on $`R`$ and $`\mathrm{\Delta }`$, the Lazy Bureaucrat Problem with no preemption can be solved in $`O(Kn^{4R\mathrm{lg}\mathrm{\Delta }})`$ for objective functions (1)-(3).

Proof: We modify the dynamic programming algorithm of Theorem 6 for this more complex situation. The set of jobs potentially available to work on in a given schedule at time $`\tau `$ are the jobs $`j`$ that have not yet been executed, for which $`d_jt_j\tau `$. Our state space will encode the complement of this set for each time $`\tau `$, specifically, the set of jobs that were executed earlier but could otherwise have been executed at time $`\tau `$.

The bounds on $`R`$ and $`\mathrm{\Delta }`$ together imply an upper bound on the number of subsets of jobs active at time $`\tau `$ that could have been executed prior to time $`\tau `$. Let $`d_{\mathrm{min}}`$ be the length of the shortest job potentially active at time $`\tau `$. We can partition all potentially active jobs into $`\mathrm{lg}\mathrm{\Delta }`$ classes, where the $`j`$th class consists of the jobs of size greater than or equal to $`2^{j1}d_{\mathrm{min}}`$ and less than $`2^jd_{\mathrm{min}}`$. The earliest possible arrival time of any class-$`j`$ job is $`\tau 2^jd_{\mathrm{min}}R`$, since each job has an $`R`$-bounded window. Only $`2^jd_{\mathrm{min}}R/2^{j1}d_{\mathrm{min}}=2R`$ jobs from class $`j`$ can be executed within this window. Summing over all the classes implies that at most $`2R\mathrm{lg}\mathrm{\Delta }`$ jobs potentially active at time $`\tau `$ could have been executed in a non-preemptive schedule by time $`\tau `$. As before the choice of weights on the edges determines the metric that is optimized.

The time bound on the running time follows by observing that each of the $`Kn^{(2R\mathrm{lg}\mathrm{\Delta })}`$ states has outdegree at most $`2R\mathrm{lg}\mathrm{\Delta }`$. $`\mathrm{}`$

#### 2.2.3 Jobs Having a Common Release Time

In the next version of the problem all jobs are released at time zero, i.e., $`a_i=0`$ for all $`i`$. This problem can be solved in pseudo-polynomial time by dynamic programming, specifically, reducing the problem to that of finding the shortest path in a directed acyclic graph. The dynamic programming works because of the following structural result: There exists an optimal schedule that executes the jobs Earliest Due Date (EDD).

In fact this problem is a special case of the following general problem: Minimizing the weighted sum of jobs not completed by their deadlines. A similar problem was solved by , using the same structural result.

###### Theorem 9

The LBP can be solved in pseudo-polynomial time for all three metrics when all jobs have a common release time. Specifically, let $`K=\mathrm{max}_id_i`$; then the running time is $`O(Kn).`$

## 3 LBP: Preemption

In this section we consider the Lazy Bureaucrat Problem in which jobs may be preempted: a job in progress can be set aside, while another job is processed, and then possibly resumed later. It is important to distinguish among different constraints that specify which jobs are available to be processed. We consider three natural choices of such constraints:

In order to work on job $`i`$ at time $`\tau `$, we require only that the current time $`\tau `$ lies within the job’s interval $`I_i`$: $`a_i\tau d_i`$.

In order to work on job $`i`$ at time $`\tau `$, we require not only that the current time $`\tau `$ lies within the job’s interval $`I_i`$, but also that the job has a chance to be completed, e.g., if it is processed without interruption until completion.

This condition is equivalent to requiring that $`\tau c_i^{}`$, where $`c_i^{}=d_it_i+y_i`$ is the adjusted critical time of job $`i`$: $`c_i^{}`$ is the latest possible time to start job $`i`$, in order to meet its deadline $`d_i`$, given that an amount $`y_i`$ of the job has already been completed.

In order to work on job $`i`$, we require that $`\tau I_i`$. Further, we require that any job that is started is eventually completed.

We divide this section into subsections, where each subsection considers one of the three objective functions (1)–(3) from Section 1.1, in which the goals are to minimize (1) the total time working (regardless of which jobs are completed), (2) the weighted sum of completed jobs, or (3) the makespan of the schedule (the “go home” time). For each metric we see that the constraints on preemption can dramatically affect the complexity of the problem.

Constraint III makes the LBP with preemption quite similar to the LBP with no preemption. In fact, if all jobs arrive at the same time ($`a_i=0`$ for all $`i`$), then the three objective functions are equivalent, and the problem is hard:

###### Theorem 10

The LBP with preemption, under constraint III (one must complete any job that is begun), is (weakly) NP-complete and hard to approximate for all three objective functions.

Proof: We use the same reduction as the one given in the proof of Theorem 1. Note that any schedule for an instance given by the reduction, in which all jobs processed must be completed eventually, can be transformed into an equivalent schedule with no preemptions. This makes the problem of finding an optimal schedule with no preemption equivalent to the problem of finding an optimal schedule in the preemptive case under constraint III. $`\mathrm{}`$

Note that we cannot use a proof similar to that of Theorem 2 to show that this problem is strongly NP-complete, since preemption can lead to improved schedules in that instance.

### 3.1 Minimizing Total Time Working

###### Theorem 11

The LBP with preemption, under constraint I (one can work on any job in its interval) and objective (1) (minimize total time working), is polynomially solvable.

Proof: The algorithm schedules jobs according to latest due date (LDD), in which at all times the job in the system with the latest deadline is being processed, with ties broken arbitrarily. An exchange argument shows that this is optimal. Suppose there is an optimal schedule that is not LDD. Consider the first time in which an optimal schedule differs from LDD, and let OPT be an optimal schedule in which this time is as late as possible. Let OPT be executing a piece of job $`i`$, $`p_i`$ and LDD executes a piece of job $`j`$, $`p_j`$. We know that $`d_i<d_j`$. We want to show that we can replace the first unit of $`p_i`$ by one unit of $`p_j`$, contradicting the choice of OPT, and thereby proving the claim. If in OPT, job $`j`$ is not completely processed, then this swap is feasible, and we are done. On the other hand, if all of $`j`$ is processed in OPT, such a swap causes a unit of job $`j`$ later on to be removed, leaving a gap of one unit. If this gap cannot be filled by any other job piece, we get a schedule with less work than OPT, which is a contradiction. Therefore assume the gap can be filled, possibly causing a later unit gap. Continue this process, and at its conclusion, either a unit gap remains contradicting the optimality of OPT, or no gaps remain, contradicting the choice of OPT. $`\mathrm{}`$

###### Theorem 12

The LBP with preemption, under constraint II (one can only work on jobs that can be completed) and objective (1) (minimize total time working), is (weakly) NP-complete.

Proof: If all arrival times are the same, then this problem is equivalent to the one in which the objective function is to minimize the makespan, which is shown to be NP-complete in Theorem 16. $`\mathrm{}`$

### 3.2 Minimizing Weighted Sum of Completed Jobs

###### Theorem 13

The LBP with preemption, under constraint I (one can work on any job in its interval) and objective (2) (minimize the weighted sum of completed jobs), is polynomially solvable.

Proof: Without loss of generality, assume that jobs $`1,\mathrm{},n`$ are indexed in order of increasing deadlines. We show how to decompose the jobs into separate components that can be treated independently. Schedule the jobs according to EDD (if a job is executing and its deadline passes, preempt and execute the next job). Whenever there is a gap (potentially of size zero), where no jobs are in the system, the jobs are divided into separate components that can be scheduled independently and their weights summed. Now we focus on one such set of jobs (having no gaps). We modify the EDD schedule by preempting a job $`\epsilon `$ units of time before it completes. Then we move the rest of the jobs of the schedule forward by $`\epsilon `$ time units and continue to process. At the end of the schedule, there are two possibilities. (1) the last job is interrupted because its deadline passes; in this case we obtain a schedule in which no jobs are completed; (2) the last job completes and in addition all other jobs whose deadlines have not passed are also forced to complete.

The proof is completed by noting the following:

* There is an optimal schedule that completes all of its jobs at the end; and
* The above schedule executes the maximum amount of work possible. (In other words, EDD (“minus $`\epsilon `$”) allows one to execute the maximum amount of work on jobs 1 through $`i`$ without completing any of them.)

$`\mathrm{}`$

###### Theorem 14

The LBP with preemption, under constraint II (one can only work on jobs that can be completed) and objective (2) (minimize the weighted sum of completed jobs), is (weakly) NP-complete.

Proof: Consider the LBP under constraint II, where the objective is to minimize the makespan. The proof of Theorem 16 will have hard instances where all jobs have the same arrival time, and where the optimal solution completes any job that it begins. Thus, for these instances the metric of minimizing the makespan is equivalent to the metric of minimizing the weighted sum of completed jobs, for weights proportional to the processing times. $`\mathrm{}`$

### 3.3 Minimizing Makespan: Going Home Early

We assume now that the bureaucrat’s goal is to go home as soon as possible.

We begin by noting that if the arrival times are all the same ($`a_i=0`$, for all $`i`$), then the objective (3) (go home as soon as possible) is in fact equivalent to the objective (1) (minimize total time working), since, under any of the three constraints I–III, the bureaucrat will be busy nonstop until he can go home.

Observe that if the deadlines are all the same ($`d_i=D`$, for all $`i`$), then the objectives (1) and (3) are quite different. Consider the following example. Job 1 arrives at time $`a_1=0`$ and is of length $`t_1=2`$, job 2 arrives at time $`a_2=0`$ and is of length $`t_2=9`$, job 3 arrives at time $`a_3=8`$ and is of length $`t_3=2`$, and all jobs have deadline $`d_1=d_2=d_3=10`$. Then, in order to minimize total time working, the bureaucrat will do jobs 1 and 3, a total of 4 units of work, and will go home at time 10. However, in order to go home as soon as possible, the bureaucrat will do job 2, performing 9 units of work, and go home at time 9 (since there is not enough time to do either job 1 or job 3).

###### Theorem 15

The LBP with preemption, under constraint I (one can do any job in its interval) and objective (3) (go home as early as possible), is polynomially solvable.

Proof: The algorithm is to schedule by Latest Due Date (LDD). The proof is similar to the one given in Theorem 11. $`\mathrm{}`$

If instead of constraint I we impose constraint II, the problem becomes hard:

###### Theorem 16

The LBP with preemption, under constraint II (one can only work on jobs that can be completed) and objective (3) (go home as early as possible), is (weakly) NP-complete, even if all arrival times are the same.

Proof: We give a reduction from Subset Sum. Consider an instance of Subset Sum given by a set $`S`$ of $`n`$ positive integers, $`x_1`$, $`x_2,\mathrm{},x_n`$, and target sum $`T`$. We construct an instance of the required version of the LBP as follows. For each integer $`x_i`$, we have a job $`i`$ that arrives at time $`a_i=0`$, has length $`t_i=x_i`$, and is due at time $`d_i=T+x_i\epsilon `$, where $`\epsilon `$ is a small constant (it suffices to use $`\epsilon =\frac{1}{3n}`$). In addition, we have a “long” job $`n+1`$, with length $`t_{n+1}>T`$, that arrives at time $`a_{n+1}=0`$ and is due at time $`d_{n+1}=T2\epsilon +t_{n+1}`$. We claim that it is possible for the bureaucrat to go home by time $`T`$ if and only if there exists a subset of $`\{x_1,\mathrm{},x_n\}`$ that sums to exactly $`T`$.

If there is a subset of $`\{x_1,\mathrm{},x_n\}`$ that sums to exactly $`T`$, then the bureaucrat can perform the corresponding subset of jobs (of total length $`T`$) and go home at time $`T`$; he is able to avoid doing any of the other jobs, since their critical times fall at an earlier time ($`T\epsilon `$ or $`T2\epsilon `$), making it infeasible to begin them at time $`T`$, by our assumption.

If, on the other hand, the bureaucrat is able to go home at time $`T`$, then we know the following:

1. The bureaucrat must have just completed a job at time $`T`$.

He cannot quit a job and go home in the middle of a job, since the job must have been completable at the instant he started (or restarted) working on it, and it remains completable at the moment that he would like to quit and go home.
2. The bureaucrat must have been busy the entire time from 0 until time $`T`$.

He is not allowed to be idle for any period of time, since he could always have been working on some available job, e.g., job $`J_{n+1}`$.
3. If the bureaucrat starts a job, then he must finish it.

First, we note that if he starts job $`J_i`$ and does at least $`\epsilon `$ of it, then he must finish it, since at time $`T`$ less than $`x_i\epsilon `$ remains to be done of the job, and it is not due until time $`T\epsilon +x_i`$, making it feasible to return to the job at time $`T`$ (so that he cannot go home at time $`T`$).

Second, we must consider the possibility that he may perform very small amounts (less than $`\epsilon `$) of some jobs without finishing them. However, in this case, the total amount that he completes of these barely started jobs is at most $`n\epsilon \frac{1}{3}`$. This is a contradiction, since his total work time consists of this fractional length of time, plus the sum of the integral lengths of the jobs that he completed, which cannot add up to the integer $`T`$. Thus, in order for him to go home at exactly time $`T`$, he must have completed every job that he started.

Finally, note that he cannot use job $`J_{n+1}`$ as “filler”, and do part of it before going home at time $`T`$, since, if he starts it and works at least time $`2\epsilon `$ on it, then, by the same reasoning as above, he will be forced to stay and complete it. Thus, he will not start it at all, since he cannot complete it before time $`T`$ (recall that $`t_{n+1}>T`$).

We conclude that the bureaucrat must complete a set of jobs whose lengths sum exactly to $`T`$.

Thus, we have reduced Subset Sum to our problem, showing that it is (weakly) NP-complete.

Note that the LBP we have constructed has non integer data. However, we can “stretch” time to get an equivalent problem in which all the data is integral. Letting $`\epsilon =\frac{1}{3n}`$, we multiply all job lengths and due dates by $`3n`$.

$`\mathrm{}`$

Remark. Hepner and Stein  recently published a pseudo-polynomial-time algorithm for this problem, thus resolving an open problem from an earlier version of this paper .

We come now to one of the main results of the paper. We emphasize this result because it uses a rather sophisticated algorithm and analysis in order to show that, in contrast with the case of identical arrival times, the LBP with identical deadlines is polynomially solvable. Specifically, the problems addressed in Theorems 16 and 17 are identical except that the flow of time is reversed. Thus, we demonstrate that in contrast to most classical scheduling problems, in the LBP, when time flows in one direction, the problem is NP-hard, whereas when the flow of time is reversed, the problem is polynomial-time solvable.

The remainder of this section is devoted to proving the following theorem:

###### Theorem 17

The LBP with preemption, under constraint II (one can only work on jobs that can be completed) and objective (3) (go home as early as possible), is solvable in polynomial time if all jobs have the same deadlines ($`d_i=D`$, for all $`i`$).

We begin with a definition a “forced gap:” There is a forced gap starting at time $`\tau `$ if $`\tau `$ is the earliest time such that the total work arriving by time $`\tau `$ is less than $`\tau `$. This (first) forced gap ends at the arrival time, $`\tau ^{}`$, of the next job. Subsequently, there may be more forced gaps, each determined by considering the scheduling problem that starts at the end, $`\tau ^{}`$, of the previous forced gap. We note that a forced gap can have length zero.

Under the “go home early” objective, we can assume, without loss of generality, that there are no forced gaps, since our problem really begins only at the time $`\tau ^{}`$ that the last forced gap ends. (The bureaucrat is certainly not allowed to go home before the end $`\tau ^{}`$ of the last forced gap, since more jobs arrive after $`\tau ^{}`$ that can be processed before their deadlines.) While an optimal schedule may contain gaps that are not forced, the next lemma implies that there exists an optimal schedule having no unforced gaps.

###### Lemma 18

Consider the LBP of Theorem 17, and assume that there are no forced gaps. If there is a schedule having makespan $`T`$, then there is a schedule with no gaps, also having makespan $`T`$.

Proof: Consider the first gap in the schedule, which begins at time $`g`$. Because the gap is not forced, there is some job $`j`$ that is not completed, and whose critical time is at time $`g^{}g`$. This is because there must be a job that arrived before $`g`$ that is not completed in the schedule, and at time $`g`$ it is no longer feasible to complete it, and therefore its critical time is before $`g`$. The interval of time between $`g^{}`$ and $`T`$ may consist of (1) gaps, (2) work on completed jobs, and (3) work on jobs that are never completed. Consider a revised schedule in which, after time $`g^{}`$, jobs of type 3 are removed, and jobs of type 2 are deferred to the end of the schedule. (Since a job of type 2 is completed and all jobs have the same deadline, we know that it is possible to move it later in the schedule without passing its critical time. It may not be possible to move a (piece of a) job of type 3 later in the schedule, since its critical time may have passed.) In the revised schedule, extend job $`j`$ to fill the empty space. Note that there is enough work in job $`j`$ to fill the space, since a critical time of $`g^{}`$ means that the job must be executed continuously until deadline $`D`$ in order to complete it. $`\mathrm{}`$

###### Lemma 19

Consider an LBP of Theorem 17 in which there are no forced gaps. Any feasible schedule can be rearranged so that all completed jobs are ordered by their arrival times and all incomplete jobs are ordered by their arrival times.

Proof: The proof uses a simple exchange argument as in the standard proof of optimality for the EDD (Earliest Due Date) policy in traditional scheduling problems. $`\mathrm{}`$

Our algorithm checks if there exists a schedule having no gaps that completes exactly at time $`T`$. Assume that the jobs $`1,\mathrm{},n`$ are labeled so that $`a_1a_2\mathrm{}a_n`$. The main steps of the algorithm are as follows:

### The Algorithm:

1. Determine the forced gaps. This allows us to reduce to a problem having no forced gaps, which starts at the end of the last forced gap.

The forced gaps are readily determined by computing the partial sums, $`\tau _j=_{i=1}^jt_i`$, for $`j=0,1,\mathrm{},n`$, and comparing them to the arrival times. (We define $`\tau _0=0`$.) The first forced gap, then, begins at the time $`\tau =\tau _j^{}=\mathrm{min}\{\tau _j:\tau _j<a_{j+1}\}`$ and ends at time $`a_{j^{}+1}`$. ($`\tau =0`$ if $`a_1>0`$; $`\tau =\mathrm{}`$ if there are no forced gaps.) Subsequent forced gaps, if any, are computed similarly, just by re-zeroing time at $`\tau ^{}`$, and proceeding as with the first forced gap.
2. Let $`x=DT`$ be the length of time between the common deadline $`D`$ and our target makespan $`T`$. A job $`i`$ for which $`t_ix`$ is called short; jobs for which $`t_i>x`$ are called long.

If it is not possible to schedule the set of short jobs so that each is completed and they are all done by time $`T`$, then our algorithm stops and returns “NO,” concluding that going home by time $`T`$ is impossible. Otherwise, we continue with the next step of the algorithm.

The rationale for this step is the observation that any job of length at most $`x`$ must be completed in any schedule that permits the bureaucrat to go home by time $`T`$, since its critical time occurs at or after time $`T`$.
3. Create a schedule $`𝒮`$ of all of the jobs, ordered by their arrival times, in which the amount of time spent on job $`i`$ is $`t_i`$ if the job is short (so it is done completely) and is $`t_ix`$ if the job is long.

For a long job $`i`$, $`t_ix`$ is the maximum amount of time that can be spent on this job without committing the bureaucrat to completing the job, i.e., without causing the adjusted critical time of the job to occur after time $`T`$.

If this schedule $`𝒮`$ has no gaps and ends at a time after $`T`$, then our algorithm stops and returns “YES.” A feasible schedule that allows the bureaucrat to go home by time $`T`$ is readily constructed by “squishing” the schedule that we just constructed: We reduce the amount of time spent on the long jobs, starting with the latest long jobs and working backwards in time, until the completion time of the last short job exactly equals $`T`$. This schedule completes all short jobs (as it should), and does partial work on long jobs, leaving all of them with adjusted critical times that fall before time $`T`$ (and are therefore not possible to resume at time $`T`$, so they can be avoided).
4. If the above schedule $`𝒮`$ has gaps or ends before time $`T`$, then $`𝒮`$ is not a feasible schedule for the lazy bureaucrat, so we must continue the algorithm.

Our objective is to decide which long jobs to complete, that is, is there a set of long jobs to complete that will make it possible to go home by time $`T`$. This problem is solved using the dynamic programming algorithm Schedule-by-$`T`$, which is described in detail below.

### Procedure Schedule-by-$`T`$:

Let $`G_i`$ be the sum of the gap lengths that occur before time $`a_i`$ in schedule $`𝒮`$. Then, we know that in order to construct a gapless schedule, at least $`G_i/x`$ long jobs (in addition to the short jobs) from $`1,\mathrm{},i1`$ must be completed. For each $`i`$ we have such a constraint; collectively, we call these the gap constraints.

###### Claim 20

If for each gap in schedule $`𝒮`$, there are enough long jobs to be completed in order to fill the gap, then a feasible schedule ending at $`T`$ exists.

We devise a dynamic programming algorithm as follows. Let $`T(m,k)`$ be the earliest completion time of a schedule that satisfies the following:

1. It completes by time $`T`$;
2. It uses jobs from the set $`\{1,\mathrm{},k\}`$;
3. It completes exactly $`m`$ jobs and does no other work (so it may have gaps, making it an infeasible schedule);
4. It satisfies the gap constraints; and
5. It completes all short jobs (of size $`x`$).

The boundary conditions on $`T(m,k)`$ are given by:

$`T(0,0)=0`$;

$`T(0,n)=\mathrm{}`$, which implies that at least one of the jobs must be completed;

$`T(m,0)=\mathrm{}`$ for $`m>0`$;

$`T(m,k)=\mathrm{}`$ if there exist constraints such that at least $`m+1`$ jobs from $`1,\mathrm{},k`$ must be completed, some of the jobs from $`1,\mathrm{},k`$ must be completed because they are short, and some additional jobs may need to be completed because of the gap constraints. Note that this implies that $`T(0,k)`$ is equal to zero or infinity, depending on whether gap constraints are disobeyed.

In general, $`T(m,k)`$ is given by selecting the better of two options:

$$T(m,k)=\mathrm{min}\{\alpha ,\beta \},$$

where $`\alpha `$ is the earliest completion time if we choose not to execute job $`k`$ (which is a legal option only if job $`k`$ is long), giving

$$\alpha =\{\begin{array}{cc}T(m,k1)\hfill & \text{if }t_k>x\hfill \\ \mathrm{}\hfill & \text{otherwise,}\hfill \end{array}$$

and $`\beta `$ is the earliest completion time if we choose to execute job $`k`$ (which is a legal option only if the resulting completion time is by time $`T`$), giving

$$\beta =\{\begin{array}{cc}\mathrm{max}(a_k+t_k,T(m1,k1)+t_k)\hfill & \text{if this quantity is }T\hfill \\ \mathrm{}\hfill & \text{otherwise.}\hfill \end{array}$$

###### Lemma 21

There exists a feasible schedule completing at time $`T`$ if and only if there exists an $`m`$ for which $`T(m,n)<\mathrm{}`$.

Proof: If $`T(m,n)=\mathrm{}`$ for all $`m`$, then, since the gap constraints apply to any feasible schedule, and it is not possible to find such a schedule for any number of jobs $`m`$, there is no feasible schedule that completes on or before $`T`$.

If there exists an $`m`$ for which $`T(m,n)<\mathrm{}`$, let $`m^{}`$ be the smallest such $`m`$. Then, by definition, $`T(m^{},n)T`$. We show that the schedule $`𝒮^{}`$ obtained by the dynamic program can be made into a feasible schedule ending at $`T`$. Consider jobs that are not completed in the schedule $`𝒮^{}`$; we wish to use some of them to “fill in” the schedule to make it feasible, as follows.

Ordered by arrival times of incomplete jobs, and doing up to $`t_ix`$ of each incomplete job, fill in the gaps. Note that by the gap constraints, there is enough work to fill in all gaps. There are two things that may make this schedule infeasible: (i) Some jobs are worked on beyond their critical times, and (ii) the last job to be done must be a completed one.

(i). Fixing the critical time problem: Consider a job $`i`$ that is processed at some time, beginning at $`\tau `$, after its critical time, $`c_i`$. We move all completed job pieces that fall between $`c_i`$ and $`T`$ to the end of the schedule, lining them up to end at $`T`$; then, we do job $`i`$ from time $`c_i`$ up until this batch of completed jobs. This is legal because all completed jobs can be pushed to the end of the schedule, and job $`i`$ cannot complete once it stops processing.

(ii). Fixing the last job to be a complete one: Move a “sliver” of the last completed job to just before time $`T`$. If this is not possible (because the job would have to be done before it arrives), then it means that we must complete one additional job, so we consider $`m^{}+1`$, and repeat the process.

Note that a technical difficulty arises in the case in which the sum of the gap lengths is an exact multiple of $`x`$: Do we have to complete an additional job or not? This depends on whether we can put a sliver of a completed job at $`T`$. There are several ways to deal with this issue, including conditioning on the last completed job, modifying the gap constraint, or ignoring the problem and fixing it if it occurs (that is if we cannot put a sliver, then add another job which must be completed to the gap constraint). $`\mathrm{}`$

This completes the proof of our main theorem, Theorem 17.

Remark. Even if all arrival times are the same, and deadlines are the same, and data is integer, an optimal solution may not be integer. In fact, there may not be an optimal solution, only a limiting one, as the following example shows: Let $`a_i=0`$ and $`d_i=100`$, for all $`i`$. Jobs $`1,\mathrm{},n1`$ have length 51, while job $`n`$ has length $`t_n=48`$. A feasible schedule executes $`\epsilon `$ of each of the first $`n1`$ jobs, where $`\epsilon >1/(n2)`$, and all of job $`n`$, so the total work done is $`(n1)\epsilon +48>(n1)/(n2)+48`$. Note that each of the first $`n1`$ jobs have $`51\epsilon `$ remaining to do, while there is only time $`52(n1)\epsilon `$ left before the deadline. Now, by making $`\epsilon `$ arbitrarily close to $`1/(n2)`$, we can make the schedule better and better.

## Acknowledgements

We thank the referees for constructive comments and suggestions that improved the presentation of the paper.


format: text

text:
# BPS Walls and Junctions in 𝒩=1 SUSY Nonlinear Sigma Models

## 1 Introduction

Supersymmetric theories provides the most attractive possibility for unified theories beyond the standard model. . In recentl years there have been intensive studies on models with extra dimensions, ,  where our world is assumed to be realized on an extended topological defects such as domain walls or various branes. Supersymmetry can be combined with this brane-world scenario and helps the construction of the extended objects.

In order to consider models with extra dimensions, we need to discuss supersymmetric theories in spacetime with dimensions higher than four. They should have at least eight supercharges. These SUSY are so restirictive that the nontrivial interactions require the nonlinearity of kinetic term (nonlinear sigma model) if there are only hypermultiplets .

Our purpose is to study the nonlinear sigma model in a simpler context of $`𝒩=1`$ SUSY theories in four dimenions to obtain walls and/or junctions as BPS solutions. This is interesting in itself, and will serve as a starting point for a more difficult case of larger number of SUSY charges. We find a nonlinear sigma model with a single chiral scalar field is also obtained which admits our $`Z_3`$ symmetric junction solution as an exact BPS solution. We find that this single field model has a moduli space with $`S^1`$ topology and that it admits BPS walls and junctions connecting arbitrary points in the moduli space. We also find other nonlinear sigma models with several chiral scalar superfields which admit a new exact junction solutions connecting $`N`$ discrete vacua. The model and the solution are generalizations of our original $`Z_3`$ symmetric vacua to a generic $`N`$ discrete vacua including models with arbitrary number of asymmetric vacua. We deal with classical field theories in this paper and will postpone to discuss questions on quantization and quantum effects for subsequent studies.

## 2 Nonlinear sigma models with exact junction solutions

Requiring a single conserved supercharge for a general nonlinear sigma model with a Kähler potential $`K`$ and a superpotential $`𝒲`$, the $`1/4`$ BPS equation is given by

$$2\frac{A^i}{z}=\mathrm{\Omega }K^{ij^{}}(A,A^{})\frac{𝒲^{}}{A^j},$$
(1)
where $`z=x^1+ix^2`$ is the complex coordinate, $`K^{ij^{}}`$ is the Kähler metric of the nonlinear sigma model, and the constant phase factor $`\mathrm{\Omega }`$ is given by the central charges which correspond to boundary conditions determining the orientation of junction. Previously we have obtained the first analytic solution of $`1/4`$ BPS junction in a model with a number of chiral scalar fields with $`U(1)\times U(1)`$ gauge interactions . The same junction configuration turns out to be a BPS solution of a simpler model with only chiral scalar fields.

There are four chiral scalar superfields $`_i,i=1,2,3`$ and $`\widehat{T}`$ with the minimal kinetic term. The linear sigma model with $`Z_3`$ symmetric junction solution can be reduced to the following form of superpotential

$$𝒲=\frac{1}{2}\left[\sqrt{3}\widehat{T}\underset{j=1}{\overset{3}{}}\left(\sqrt{3}\widehat{T}\mathrm{e}^{i\frac{2\pi }{3}j}\right)_j^2\right].$$
(2)
There are three isolated SUSY vacua at $`\widehat{T}=\frac{1}{\sqrt{3}}\mathrm{e}^{i\frac{2\pi }{3}j},_j=\pm 1,_k=0,kj.`$(j=1, 2, 3). The $`\frac{1}{4}`$ BPS equations (1) with $`\mathrm{\Omega }=1`$ turn out

$$2\frac{_j}{z}=\left(\mathrm{e}^{i\frac{2\pi }{3}j}\sqrt{3}\widehat{T}^{}\right)_j^{},$$
(3)
$$2\frac{\widehat{T}}{z}=\frac{\sqrt{3}}{2}\left(1\underset{j=1}{\overset{3}{}}_j^2\right).$$
(4)
It is convenient to define the following auxiliary quantities taking real values

$$f_j\mathrm{exp}\left(\frac{1}{2}\left(\mathrm{e}^{i\frac{2\pi }{3}j}z+\mathrm{e}^{i\frac{2\pi }{3}j}z^{}\right)\right),j=1,2,3.$$
(5)
which satisfy $`_{j=1}^3f_j=1`$. The exact BPS solution for a junction connecting three vacua is given by

$$\widehat{T}=\frac{1}{\sqrt{3}}\frac{\underset{j=1}{\overset{3}{}}\mathrm{e}^{i\frac{2\pi }{3}j}f_j}{_{k=1}^3f_k},_j=\frac{f_j}{_{k=1}^3f_k}.$$
(6)
We have shown that the configuration (6) on a circle at infinity $`|z|\mathrm{}`$ reduces to a collection of three walls separating three vacuum regions, which are represented by three straight line segments connecting three vacua in the complex plane of superpotential .

We observe that the junction solution is a mapping from a two-dimensional base space $`x^1,x^2`$ to the complex scalar fields $`_j,j=1,2,3`$ and $`\widehat{T}`$. Therefore we can reexpress the complex scalar fields $`_j,j=1,2,3`$ in favor of the complex coordinate $`z=x^1+ix^2`$ and then invert the relation between $`\widehat{T}`$ and $`z`$ to express everything in favor of $`\widehat{T}`$ eventually. In particular, we can express the right-hand side of the BPS equation for $`\widehat{T}`$ in Eq.(4) solely in terms of $`\widehat{T}`$ by this process. The resulting BPS equation can be interpreted as the BPS equation (1) in a nonlinear sigma model with appropriate superpotential and Kähler metric. Using Eqs.(4), and (6), we obtain

$`2{\displaystyle \frac{\widehat{T}}{z}}`$ $`=`$ $`{\displaystyle \frac{\sqrt{3}}{2}}\left(1{\displaystyle \underset{j=1}{\overset{3}{}}}_j^2\right)={\displaystyle \frac{\sqrt{3}}{2}}\left(1{\displaystyle \frac{\underset{j=1}{\overset{3}{}}f_j^2}{\left(_{k=1}^3f_k\right)^2}}\right)=\sqrt{3}{\displaystyle \frac{f_1f_2+f_2f_3+f_3f_1}{\left(_{k=1}^3f_k\right)^2}}`$ (7)
$`=`$ $`\sqrt{3}{\displaystyle \frac{f_1f_2+\frac{1}{f_1}+\frac{1}{f_2}}{\left(f_1+f_2+\frac{1}{f_1f_2}\right)^2}}=\sqrt{3}{\displaystyle \frac{f_1f_2\left(f_1^2f_2^2+f_1+f_2\right)}{\left(f_1f_2\left(f_1+f_2\right)+1\right)^2}},`$
where we have eliminated $`f_3`$ by means of the identity $`_jf_j=1`$. Similarly we can reexpress the field $`\widehat{T}=\widehat{T}_R+i\widehat{T}_I`$ as

$$\sqrt{3}\widehat{T}_R=\frac{\frac{f_1+f_2}{2}+f_3}{_{k=1}^3f_k}=\frac{\frac{f_1f_2(f_1+f_2)}{2}+1}{f_1f_2(f_1+f_2)+1}$$
(8)
$$\sqrt{3}\widehat{T}_I=\frac{\frac{\sqrt{3}}{2}(f_1f_2)}{f_1+f_2+\frac{1}{f_1f_2}}=\frac{\frac{\sqrt{3}}{2}f_1f_2(f_1f_2)}{f_1f_2(f_1+f_2)+1}.$$
(9)
Therefore we finally find that

$$2\frac{\widehat{T}}{z}=\frac{1}{\sqrt{3}}\left(13\widehat{T}_R^23\widehat{T}_I^2\right)=\frac{1}{\sqrt{3}}\left(1|\sqrt{3}\widehat{T}|^2\right).$$
(10)
The resulting equation should be identified with a $`\frac{1}{4}`$ BPS equation (1) for a nonlinear sigma model. We find that the superpotential is linear in $`\widehat{T}`$ and the Kähler metric is nontrivial

$$K_{\widehat{T}\widehat{T}^{}}=\frac{3}{1|\sqrt{3}\widehat{T}|^2},𝒲=\sqrt{3}\widehat{T}.$$
(11)
We emphasize that the above choice is not a matter of convenience, and that the holomorphy forces us to choose the superpotential as the chiral scalar superfield $`\widehat{T}`$ itself except for the freedom of a possible proportionality constant $`𝒲/\widehat{T}`$. The Kähler potential is given by

$$K(\widehat{T},\widehat{T}^{})=^{3|\widehat{T}|^2}\frac{dx}{x}\mathrm{log}\frac{1}{1x}.$$
(12)
From the above procedure, we see that the nonlinear sigma model with a single chiral scalar superfield is unique modulo usual freedom of holomorphic field redefinitions, if we require that it allows the exact junction (6) as the $`\frac{1}{4}`$ BPS solution.

By using a rescaled field $`T\sqrt{3}\widehat{T}`$, we obtain the nonlinear sigma model

$$_{\mathrm{NLSM}}=\frac{1}{1|T|^2}_\mu T^{}^\mu T\left(1|T|^2\right).$$
(13)
We observe that the nonlinear sigma model has continuous vacua at $`|T|=1`$, corresponding to the continuous family of singularities of the Kähler metric. The moduli space has a topology of a circle.

Now we shall show that there are $`\frac{1}{2}`$ BPS wall solutions connecting any two arbitrary points in this moduli space. Since an orthogonal section of the $`\frac{1}{2}`$ BPS configuration should follow a straight line trajectory in the complex plane of the superpotential , we just need to construct a straight line connecting two vacua in the moduli space, thanks to our choice of the superpotential as the field variable. Let us define a variable taking a real value $`1\stackrel{~}{T}1`$ along the straight line connecting from $`T=\mathrm{e}^{i\alpha _1}`$ and $`T=\mathrm{e}^{i\alpha _2}`$ as shown in Fig. 1 (a)

$$T=\frac{\mathrm{e}^{i\alpha _2}+\mathrm{e}^{i\alpha _1}}{2}+\frac{\mathrm{e}^{i\alpha _2}\mathrm{e}^{i\alpha _1}}{2}\stackrel{~}{T}.$$
(14)
By assuming the one-dimensional profile, we obtain the $`\frac{1}{2}`$ BPS equation for the wall

$$\frac{d\stackrel{~}{T}}{dx}=\mathrm{sin}\frac{\alpha _2\alpha _1}{2}\left[1\left(\stackrel{~}{T}\right)^2\right]$$
(15)
where we have taken the constant phase factor in Eq.(1) as $`\mathrm{\Omega }=i\mathrm{e}^{i\frac{\alpha _2+\alpha _1}{2}}`$ in order to orient the wall along the $`x=x^1`$ direction. We can recognize the familiar BPS equation to give the wall solution and find

$$\stackrel{~}{T}=\mathrm{tanh}\left(x\mathrm{sin}\frac{\alpha _2\alpha _1}{2}\right)$$
(16)
$$T=\frac{\mathrm{e}^{i\alpha _2}\mathrm{e}^{x\mathrm{sin}\frac{\alpha _2\alpha _1}{2}}+\mathrm{e}^{i\alpha _1}\mathrm{e}^{x\mathrm{sin}\frac{\alpha _2\alpha _1}{2}}}{\mathrm{e}^{x\mathrm{sin}\frac{\alpha _2\alpha _1}{2}}+\mathrm{e}^{x\mathrm{sin}\frac{\alpha _2\alpha _1}{2}}}.$$
(17)
More surprisingly, we can show that there exist exact $`\frac{1}{4}`$ BPS junction solutions connecting any number of ordered points $`\mathrm{e}^{i\alpha _j},j=1,\mathrm{},N`$ in the moduli space as shown in Fig. 1 (b). To obtain the junction solution, let us define the following auxiliary quantities $`f_j`$ generalized from Eq.(5)

$$f_j\mathrm{exp}\left(\frac{1}{2}\left(\mathrm{e}^{i\alpha _j}z+\mathrm{e}^{i\alpha _j}z^{}\right)\right),j=1,\mathrm{},N.$$
(19)
Let us define an auxiliary variable $`\eta `$ as $`\eta 2\mathrm{log}\left(_{j=1}^Nf_j\right).`$Then we obtain

$$\frac{\eta }{z}=\frac{\underset{k=1}{\overset{N}{}}\mathrm{e}^{i\alpha _k}f_k}{_{j=1}^Nf_j},\frac{^2\eta }{zz^{}}=\frac{1}{2}\left[1\left|\frac{\eta }{z}\right|^2\right],$$
(20)
If we take the following Ansatz

$$T=\frac{\eta }{z^{}}=\frac{\underset{k=1}{\overset{N}{}}\mathrm{e}^{i\alpha _k}f_k}{_{j=1}^Nf_j},$$
(21)
we find that the field $`T`$ satisfies the $`\frac{1}{4}`$ BPS equation (1) for the nonlinear sigma model (13) with the Kähler metric $`K_{TT^{}}=1/(1|T|^2)`$ and the superpotential $`𝒲=T`$

$$2\frac{T}{z}=1\left|\frac{\eta }{z}\right|^2=1\left|T\right|^2.$$
(22)
The energy density of the junction with a choice of $`5`$ points in moduli space is shown in Fig. 2.

The kinetic term of the nonlinear sigma model is nonnegative definite only for $`|T|1`$. It is interesting to observe that the moduli space $`|T|=1`$ of the nonlinear sigma model forms a natural boundary of the field space beyond which the kinetic term of the nonlinear sigma model is no longer positive definite.

Another peculiar feature of the nonlinear sigma model (13) is that the boundary condition can be deformed continuously since the moduli space of vacua is continuous. The walls and junctions are stable as long as the boundary condition is fixed. However, the adiabatic change of the boundary condition can make the adiabatic deformation of the walls and junctions.

## 3  NLSM with discrete vacua and junction solution

We shall work out the model which has the $`N`$-junction as a solution of $`\frac{1}{4}`$ BPS equation. Let us introduce the chiral scalar superfields $`_j,j=1,\mathrm{},N`$ besides the chiral scalar superfield $`T`$. We assume the minimal kinetic term for these additional fields $`_j`$. However, we leave the Kähler metric $`K_{TT^{}}`$ of the field $`T`$ to be an arbitray function of $`T,T^{}`$ and will determine it by requiring that the model possesses a $`N`$-junction as a solution of the $`\frac{1}{4}`$ BPS equation. We assume a generalization of the superpotential in Eq.(2)

$$𝒲=\frac{1}{2}\left[T\underset{j=1}{\overset{N}{}}\left(T\mathrm{e}^{i\alpha _j}\right)_j^2\right]$$
(23)
where the parameters $`\alpha _j,j=1,\mathrm{},N`$ specify the position of discrete vacua as we show below, and becomes $`\alpha _j=2\pi j/N`$ for the $`Z_N`$ symmetric case.

The SUSY vacuum condition gives two conditions in this model

$$\left(\mathrm{e}^{i\alpha _j}T\right)_j=0,j=1,\mathrm{},N,$$
(24)
$$K^{TT^{}}\frac{1}{2}\left|1\underset{j=1}{\overset{N}{}}_j^2\right|^2=0.$$
(25)
We find that there are two types of the SUSY vacua :

1. The $`j`$-th condition (24) is satisfied if the field T takes a particular value $`T=\mathrm{e}^{i\alpha _j}`$ for an integer $`j`$. Then the other conditions (24) imply $`_k=0`$ for $`kj`$. Assuming that the Kähler metric is not singular at the point $`T=\mathrm{e}^{i\alpha _j}`$, the second condition (25) is only satisfied by $`_j=\pm 1`$.

$$T=\mathrm{e}^{i\alpha _j},_j=\pm 1,_k=0,kj,j=1,\mathrm{},N.$$
(26)
We will check later that the Kähler metric is indeed not singular at this point. This is the $`N`$ discrete SUSY vacua given by stationary points of the superpotential.
2. If $`T\mathrm{e}^{i\alpha _j},j=1,\mathrm{},N`$, all the other fields have to vanish $`_j=0`$ to satisfy Eq.(24). The other condition (25) can only be satisfied by a singularity of the Kähler metric

$$K_{TT^{}}=\mathrm{}.$$
(27)

The $`\frac{1}{4}`$ BPS equations (1) for $`_j`$ and $`T`$ are given by

$$2\frac{_j}{z}=\left(\mathrm{e}^{i\alpha _j}T^{}\right)_j^{},$$
(28)
$$2\frac{T}{z}=K^{TT^{}}\frac{1}{2}\left(1\underset{j=1}{\overset{N}{}}_j^2\right).$$
(29)
Using the auxiliary quantities $`f_j`$ defined in Eq.(19), we assume the following Ansatz for the junction

$$T=\frac{\underset{j=1}{\overset{N}{}}\mathrm{e}^{i\alpha _j}f_j}{_{k=1}^Nf_k},_j=\frac{f_j}{_{k=1}^Nf_k}.$$
(30)
By using identities

$$\frac{f_j}{z}=\frac{1}{2}\mathrm{e}^{i\alpha _j}f_j,$$
(31)
$`{\displaystyle \frac{}{z}}\left({\displaystyle \frac{f_j}{_{k=1}^Nf_k}}\right)`$ $`=`$ $`{\displaystyle \frac{f_j}{_{k=1}^Nf_k}}{\displaystyle \frac{1}{2}}\left(\mathrm{e}^{i\alpha _j}T^{}\right)`$ (32)
we find that the $`\frac{1}{4}`$ BPS equation for $`_j`$ in Eq.(28) is satisfied. Then the remaining $`\frac{1}{4}`$ BPS equation for $`T`$ is also satisfied if and only if the Kähler metric of the field $`T`$ is given by

$`K_{TT^{}}`$ $`=`$ $`{\displaystyle \frac{\frac{1}{2}\left(1\underset{j=1}{\overset{N}{}}_j^2\right)}{2\frac{T}{z}}}={\displaystyle \frac{1\frac{\underset{j=1}{\overset{N}{}}f_j^2}{\left(_{k=1}^Nf_k\right)^2}}{2\left(1\frac{|_{l=1}^N\mathrm{e}^{i\alpha _l}f_l|^2}{\left(_{m=1}^Nf_m\right)^2}\right)}}`$ (33)
$`=`$ $`{\displaystyle \frac{1\frac{\underset{j=1}{\overset{N}{}}f_j^2}{\left(_{k=1}^Nf_k\right)^2}}{2\left(1|T|^2\right)}}={\displaystyle \frac{2\frac{\underset{j<l}{}f_jf_k}{\left(_{k=1}^Nf_k\right)^2}}{2\left(1|T|^2\right)}}.`$
Here we have expressed the metric in terms of the auxiliary quantities $`f_j`$ as an intermediate step. The numerator of the right-hand side can be expressed in terms of the $`T=T_R+iT_I`$, since $`f_j`$ are given in terms of $`z`$ which can be expressed in terms of $`T_R`$ and $`T_I`$. Therefore we have solved the $`\frac{1}{4}`$ BPS equations and obtained the Kähler metric of the nonlinear sigma model implicitly through Eqs.(19), (30), and (33). It is gratifying to find that the resulting Kähler metric is real. This is a nontrivial requirement which should be imposed on the Kähler metric. The asymptotic behavior of the solution precisely reproduces the expected vacuum configuration and the connecting wall configurations. Therefore we have found the $`\frac{1}{4}`$ BPS junction solution connecting $`N`$ discrete vacua.

We now examine the properties of the Kähler metric (33). The singularity can occur only on a circle $`|T|=1`$. However, the junction solution can never touch the circle as long as $`z`$ is finite. The circle can be reached only asymptotically as $`|z|\mathrm{}`$. In fact, the junction solution approaches asymptotically along a generic direction to one of the discrete vacua, say $`\mathrm{e}^{i\alpha _j}`$. On the other hand, the numerator is such that it also vanishes precisely at these vacua and the Kähler metric becomes finite at the discrete vacua

$$K_{TT^{}}\frac{1}{2\left(1\mathrm{cos}(\alpha _j\alpha _{j1})\right)},$$
(34)
if the nearest vacuum to $`\mathrm{e}^{\alpha _j}`$ is at $`\mathrm{e}^{\alpha _{j1}}`$. If the nearest vacuum is at $`\mathrm{e}^{\alpha _{j+1}}`$ instead, we should replace $`\alpha _{j1}`$ by $`\alpha _{j+1}`$. This result shows that the Kähler metric is in fact nonsigular as we have assumed in analyzing the SUSY vacua. The junction asymptotically along the wall direction becomes a wall solution. In our solution, the wall is mapped to a straight line segments connecting adjacent vacua in the $`T`$ plane. The Kähler metric takes the value (34) along the straight line corresponding to the wall connecting the vacua $`T=\mathrm{e}^{\alpha _{j1}}`$ and $`T=\mathrm{e}^{\alpha _j}`$. Let us call $`R=\{T(z,z^{})𝐂,z𝐂\}`$ the image of the entire real space $`z`$ by the map $`T(z,z^{})`$ defined by the junction solution (30). Summarizing the properties of the Kähler metric, we find

1. The Kähler metric is real and positive in $`R`$.
2. The Kähler metric is never singular in $`R`$.
3. The field $`T`$ can approach asymptotically to the unit circle only at the discrete vacuum $`T=\mathrm{e}^{i\alpha _j}`$ where the Kähler metric is finite.
4. The asymptotic value of the junction solution is mapped to a straight line segments connecting these discrete vacua in the $`T`$ plane.
5. At the origin of the base space, the auxiliary quantity becomes $`f_j=1`$. In the case of $`Z_N`$ symmetric model, the field takes values $`T=0,_j=1/N`$ and the Kähler metric takes a value $`K_{TT^{}}=(N1)/(2N)`$.

These results suggest that $`R`$ is a polygon with the $`N`$ discrete vacua as vertices. It is interesting to observe that the moduli space is divided into several discrete stationary points and singular arcs as illustrated by an example in Fig.3. We expect that the kinetic term is positive definite in $`|T|1`$, and that the natural domain of definition for our nonlinear sigma model is $`|T|1`$, which turn out to be the case in models that we are going to analyze more explicitly.

Let us evaluate the Kähler metric as a function of $`T`$ more explicitly. For that purpose, we shall first take the $`Z_N`$ symmetric case. The model with junction starts from $`N=3`$. The model with $`N=3`$ turn out to give a minimal kinetic term $`K_{TT^{}}=1`$ and hence reduces to our original model in Ref.. The next model is $`N=4`$. We find that the model in fact gives a nonlinear sigma model for the field $`T`$ as

$$K_{TT^{}}=\frac{1}{2(1|T|^2)}\left[\frac{3}{4}\frac{1}{2}|T|^2\frac{1}{16}\left(T^4+T^4\right)\frac{1}{8}|T|^4\right].$$
(35)
As shown in Fig.3, there is a locus of zeros of the numerator of the Kähler metric which touches the unit circle precisely at the four discrete points $`T=\mathrm{e}^{i\frac{2\pi }{4}j},j=1,\mathrm{},4`$. This concrete example shows our general analysis clearly: the Kähler metric is singular along four arcs separated by discrete stationary points of the superpotential $`T=\mathrm{e}^{i\frac{2\pi }{4}j},j=1,\mathrm{},4`$ where the Kähler metric is finite. The region between the circle $`|T|=1`$ and the outer curve touching the circle at $`T=1,i,1,i`$ gives the region of negative kinetic term as shown in Fig. 3(a). The energy density of the junction is shown in Fig. 4.

In this model, we have also a continuous moduli space consisting of the arcs of singularities of the Kähler metric. However, even if we attempt to make a wall and/or a junction solution connecting these vacua of singularities, we find that the BPS equations are not satisfied by Ansatz similar to our previous one in Eqs.(21) or (30), since $`T`$ now has a nonlinear kinetic term in our model. It is possible that there may exist wall or junction solutions connecting these singularities of the Kähler metric. Even if they exist, however, these solutions cannot be adiabatically deformed to our solution, since the other fields $``$ take different values in two types of vacua as shown in Eqs.(26) and (27).

As another example, we shall give a model without the $`Z_N`$ symmetry. Let us take three “matter” fields $`_j,j=1,2,3`$ besides $`T`$. We choose the superpotential (23) with $`\alpha _1=\pi /2,\alpha _2=\pi /2,\alpha _3=0`$. Then we have three discrete vacua at asymmetric points $`T=1,i,i`$ on the unit circle.

We find that the Kähler metric in Eq.(33) becomes in this model

$$K_{TT^{}}=\frac{1}{4(1|T|^2)}\left(1+T+T^{}2|T|^2\frac{T^2+T^2}{2}\right).$$
(37)
The Kähler metric again has a general feature: it is finite at the discrete vacua which separate the arcs of singular points of the Kähler metric. The kinetic term is negative in the region between the circle $`|T|=1`$ and the ellipse touching the circle at three vacua $`T=1,i,i`$. The energy density of the junction is shown in Fig. 5.


text:
# Strongly Correlated Fractional Quantum Hall Line Junctions

## Abstract

We have studied a clean finite–length line junction between interacting counterpropagating single–branch fractional–quantum–Hall edge channels. Exact solutions for low–lying excitations and transport properties are obtained when the two edges belong to quantum Hall systems with different filling factors and interact via the long–range Coulomb interaction. Charging effects due to the coupling to external edge–channel leads are fully taken into account. Conductances and power laws in the current–voltage characteristics of tunneling are strongly affected by inter–edge correlations.

Two–dimensional (2D) electron systems exhibit incompressibilities when their sheet density $`n_0`$ is commensurate with the value $`B`$ of perpendicular magnetic field such that the filling factor $`\nu =2\pi \mathrm{}n_0/|eB|`$ is integer or equal to certain fractions Prange and Girvin (1990); Das Sarma and Pinczuk (1997). Such an incompressible phase is characterized by a quantized value of the Hall resistance and low–lying excitations that are localized at the boundary of the 2D system Halperin (1982); MacDonald and Středa (1984); MacDonald (1990); Wen (1990); Fröhlich and Zee (1991). When $`\nu `$ is the inverse of an odd integer, these quantum–Hall (QH) edge excitations have been shown Wen (1992) to be isomorphous to those of a single–branch chiral one–dimensional (1D) electron system Voit (1994). Similar to their nonchiral counterparts that are realized, e.g., in semiconductor quantum wires Yacoby et al. (1996) or carbon nanotubes Wilder et al. (1998), QH edges are expected Wen (1992) to exhibit power laws in electronic correlation functions that are the hallmark of Luttinger–liquid behavior Haldane (1981). Virtually no other quasi–1D electron system, however, matches the versatility of QH edges in tailoring their electronic properties which can be achieved, e.g., simply by adjusting the magnetic field and/or appropriate nanostructuring techniques. Recent applications of the cleaved–edge overgrowth method Pfeiffer et al. (1990); Grayson et al. (1996) have succeeded in creating extended uniform tunnel junctions between two integer QH edges Kang et al. (1999) or a 2D electron system and a QH edge Huber et al. (2001). Besides opening up new possibilities for electron tunneling spectroscopy Zülicke et al. (2002), these new sample geometries enable the controlled experimental study of the interplay between tunneling and interaction effects in low dimensions Finkel’stein and Larkin (1993); Fabrizio (1993); Clarke et al. (1994); Schulz (1996) that cannot be performed in conventional systems.

A diverse set of electron–correlation effects has been proposed for QH line junctions where both edge channels belong to QH systems having the same filling factorRenn and Arovas (1995); Kane and Fisher (1997); Mitra and Girvin (2001); Kollar and Sachdev (2002); Kim and Fradkin . In our work presented here, we consider the case of a clean junction where the filling factors $`\nu _\text{R}`$ and $`\nu _\text{L}`$, characterizing the respective right–moving and left–moving edges, are different. Such a situation could be realized, e.g., in samples with two mutually perpendicular 2D electron systems Huber et al. (2001) and a magnetic field properly adjusted in magnitude and direction. In the experimentally realistic limit where electrons from the two edges interact strongly via Coulomb interactions, low–lying excitations are represented by two decoupled bosonic modes that have opposite chirality. One of them, the charged mode, corresponds to fluctuations in the total electron density in the two edges and is free. The dynamics of its orthogonal complement, the neutral mode, turns out to be governed by realizations of chiral sine–Gordon models Zülicke (1999); Naud et al. (2000) that can be solved exactly for certain values of the parameter $`\stackrel{~}{\nu }=\nu _\text{R}\nu _\text{L}/|\nu _\text{R}\nu _\text{L}|`$. We use these exact solutions to calculate transport through the line junction and find that the strong inter–edge correlations significantly affect the conductance and tunneling resonances arising from translational invariance along the barrier.

Starting point of our calculations is the Hamiltonian for our model of the line junction. (See Fig. 1.) It reads $`H_\text{J}=_{L/2}^{L/2}𝑑x\left(_\text{R}+_\text{L}+_{\text{int}}+_{\text{tun}}\right)`$ where $`_{\text{R/L}}`$ describe isolated edge channels, $`_{\text{int}}`$ the inter–edge interaction, and $`_{\text{tun}}`$ uniform tunneling across the barrier:

$`_{\text{R/L}}`$ $`=`$ $`{\displaystyle \frac{1}{4\pi }}\left\{\mathrm{}v_{\text{R/L}}^{(0)}+{\displaystyle \frac{\nu _{\text{R/L}}}{2\pi }}U\right\}\left[_x\varphi _{\text{R/L}}\right]^2,`$ (1a)
$`_{\text{int}}`$ $`=`$ $`{\displaystyle \frac{\sqrt{\nu _\text{R}\nu _\text{L}}}{4\pi ^2}}\lambda U_x\varphi _\text{R}_x\varphi _\text{L},`$ (1b)
$`_{\text{tun}}`$ $`=`$ $`t\left\{\psi _\text{R}^{}(x)\psi _\text{L}(x)+\text{H.c.}\right\}.`$ (1c)
Here we denote the second–quantized annihilation operators for electrons from the two edges as $`\psi _{\text{R/L}}`$. The chiral bosonic phase fields $`\varphi _{\text{R/L}}(x)`$ are related to the respective edge densities via $`\varrho _{\text{R/L}}=\psi _{\text{R/L}}^{}\psi _{\text{R/L}}=\sqrt{\nu _{\text{R/L}}}_x\varphi _{\text{R/L}}/(2\pi )`$ and obey the commutation relations $`[\varphi _{\text{R/L}}(x),\varphi _{\text{R/L}}(x^{})]=\pm i\pi \text{sgn}(xx^{})`$. The bare (confinement–induced) electron velocities in the two edge channels are given by $`v_{\text{R/L}}^{(0)}`$, $`U`$ is the matrix element of screened Coulomb interactions, and we have taken into account the generally different interaction strengths within and between the edges by a factor $`0<\lambda 1`$. It is straightforward to diagonalize the part $`H_\text{J}_{L/2}^{L/2}𝑑x_{\text{tun}}`$, and using the bosonization identity von Delft and Schoeller (1998)

$$\psi _{\text{R/L}}(x)=\sqrt{z_{\text{R/L}}}_{\text{R/L}}e^{ix\frac{Y_{\text{R/L}}}{\mathrm{}^2}\pm i\frac{\varphi _{\text{R/L}}(x)}{(\nu _{\text{R/L}})^{1/2}}},$$
(2)
the tunneling term $`_{\text{tun}}`$ can be expressed solely in terms of bosonic phase fields as well. \[In Eq. (2), $`z_{\text{R/L}}`$ are normalization constants, $`_{\text{R/L}}`$ Klein factors, $`Y_{\text{R/L}}`$ the guiding–center coordinates of edge electrons in the direction perpendicular to the junction, and $`\mathrm{}=\sqrt{\mathrm{}c/|eB|}`$ the magnetic length.\] However, explicit expressions for normal modes in the most general case are unilluminating. We therefore proceed immediately to the special case of interest to us where strong Coulomb interactions dominate the bare electron velocities in each branch, i.e., $`\mathrm{}v_{\text{R/L}}^{(0)}U`$, and the distance between the two edges is of the order of or smaller than $`\mathrm{}`$ such that $`\lambda 1`$. It is then possible to rewrite the QH–junction Hamiltonian as $`H_\text{J}=_{L/2}^{L/2}𝑑x\left(_\text{c}+_\text{n}\right)`$ with the contributions

$`_\text{c}`$ $`=`$ $`{\displaystyle \frac{\mathrm{}v_\text{c}}{4\pi }}\left[_x\varphi _\text{c}\right]^2,`$ (3a)
$`_\text{n}`$ $`=`$ $`{\displaystyle \frac{\mathrm{}v_\text{n}}{4\pi }}\left[_x\varphi _\text{n}\right]^2+2t\sqrt{z_\text{R}z_\text{L}}\mathrm{cos}\left({\displaystyle \frac{\varphi _\text{n}}{\sqrt{\stackrel{~}{\nu }}}}+{\displaystyle \frac{x\mathrm{\Delta }}{\mathrm{}^2}}\right),`$ (3b)
for independent c(harged) and n(eutral) modes 111This actually requires also the condition $`U|t|\mathrm{}`$ to hold which is typically satisfied. No Klein factors appear in Eqs. (3) as they give rise only to an overall factor $`\pm 1`$ that can be absorbed into the tunneling matrix element Naud et al. (2000).. Their corresponding phase fields obey commutation relations $`[\varphi _{\text{c/n}}(x),\varphi _{\text{c/n}}(x^{})]=\pm \text{sgn}(\nu _\text{R}\nu _\text{L})i\pi \text{sgn}(xx^{})`$ and are related to the densities of the original right–moving and left–moving edge electrons via

$$\varrho _{\text{R/L}}=\frac{\pm \text{sgn}(\nu _\text{R}\nu _\text{L})}{2\pi \sqrt{|\nu _\text{R}\nu _\text{L}|}}\left(\nu _{\text{R/L}}_x\varphi _\text{c}\sqrt{\nu _\text{R}\nu _\text{L}}_x\varphi _\text{n}\right).$$
(4)
The velocities are $`v_\text{c}=|\nu _\text{R}\nu _\text{L}|U/(2\pi \mathrm{})`$ and $`v_\text{n}=\left(\nu _\text{R}v_\text{L}^{(0)}+\nu _\text{L}v_\text{R}^{(0)}\right)/|\nu _\text{R}\nu _\text{L}|`$, and we used the abbreviation $`\mathrm{\Delta }:=Y_\text{R}Y_\text{L}`$. We see from Eqs. (3) that the charged mode is free while the neutral–mode dynamics is that of a chiral sine–Gordon model Zülicke (1999); Naud et al. (2000). Before obtaining its solution, we interject an elaboration on observables related to electron transport.

To discuss transport properties, it is necessary to consider continuity equations and chemical potentials for the various edge densities. Denoting time by $`\tau `$, the operator for particle current (per unit length) across the barrier is

$`_\text{J}(x)`$ $`=`$ $`{\displaystyle \frac{d}{d\tau }}\varrho _\text{R}(x)={\displaystyle \frac{d}{d\tau }}\varrho _\text{L}(x),`$ (5a)
$`=`$ $`i{\displaystyle \frac{t}{\mathrm{}}}\left\{\psi _\text{R}^{}(x)\psi _\text{L}(x)\text{H.c.}\right\},`$ (5b)
In our limit of interest, its bosonized expression depends on the neutral mode only,

$$_\text{J}(x)=2\frac{t}{\mathrm{}}\sqrt{z_\text{R}z_\text{L}}\mathrm{sin}\left(\frac{\varphi _\text{n}}{\sqrt{\stackrel{~}{\nu }}}+\frac{x\mathrm{\Delta }}{\mathrm{}^2}\right).$$
(6)
It is straightforward to find a continuity equation for density $`\varrho _\text{c}:=_x\varphi _\text{c}/(2\pi )`$ associated with the charged mode,

$`0`$ $`=`$ $`{\displaystyle \frac{d}{d\tau }}{\displaystyle \frac{\varrho _\text{R}+\varrho _\text{L}}{\sqrt{|\nu _\text{R}\nu _\text{L}|}}}{\displaystyle \frac{d}{d\tau }}\varrho _\text{c},`$ (7a)
$`=`$ $`\left\{_\tau +\text{sgn}(\nu _\text{R}\nu _\text{L})v_\text{c}_x\right\}\varrho _\text{c},`$ (7b)
and the corresponding one for $`\varrho _\text{n}:=_x\varphi _\text{n}/(2\pi )`$,

$`0`$ $`=`$ $`{\displaystyle \frac{d}{d\tau }}\varrho _\text{n}{\displaystyle \frac{\text{sgn}(\nu _\text{R}\nu _\text{L})}{\sqrt{\stackrel{~}{\nu }}}}_\text{J},`$ (8a)
$`=`$ $`\left\{_\tau \text{sgn}(\nu _\text{R}\nu _\text{L})v_\text{n}_x\right\}\varrho _\text{n}.`$ (8b)
In the stationary regime, densities have no explicit time dependence. The above continuity equations then imply that they assume constant values $`\overline{\varrho }_{\text{c/n}}`$ along the junction. We can also derive expressions for local chemical potentials $`\mu _{\text{c/n}}:=\delta H_\text{J}/\delta \varrho _{\text{c/n}}i\text{sgn}(\nu _\text{R}\nu _\text{L})[H_\text{J},\varphi _{\text{c/n}}]`$ associated with the charged and neutral modes:

$`\mu _\text{c}(x)`$ $`=`$ $`2\pi \mathrm{}v_\text{c}\varrho _\text{c}(x),`$ (9a)
$`\mu _\text{n}(x)`$ $`=`$ $`2\pi \mathrm{}v_\text{n}\varrho _\text{n}(x)`$ (9b)
$`+{\displaystyle \frac{\pi \mathrm{}}{\sqrt{\stackrel{~}{\nu }}}}{\displaystyle _{\frac{L}{2}}^{\frac{L}{2}}}𝑑x^{}_\text{J}(x^{})\text{sgn}(xx^{}).`$
Specializing these to the stationary limit, we find

$`\mu _\text{c}(x)`$ $`=`$ $`2\pi \mathrm{}v_\text{c}\overline{\varrho }_\text{c}=\text{const.},`$ (10a)
$`\mu _\text{n}(\pm L/2)`$ $`=`$ $`2\pi \mathrm{}v_\text{n}\overline{\varrho }_\text{n}\pm {\displaystyle \frac{\pi \mathrm{}}{\sqrt{\stackrel{~}{\nu }}}}I_\text{J},`$ (10b)
where $`I_\text{J}:=_{L/2}^{L/2}𝑑x_\text{J}(x)`$ is the total current flowing through the junction. The values of $`\overline{\varrho }_{\text{c/n}}`$ and $`I_\text{J}`$ can be related to chemical potentials in the external leads that connect the QH junction to reservoirs (see Fig. 1), which we proceed to show now.

In a real setup as sketched in Fig. 1a, edge channels away from the junction are not coupled via tunneling or interactions anymore. However, for each of these chiral 1D leads, Coulomb interactions between electrons at the same edge still give the dominant contribution to the edge–magnetoplasmon velocity Zülicke and MacDonald (1996). We therefore model the dynamics of electrons in regions $`|x|>L/2`$ by the lead Hamiltonian $`H_\text{E}=\left\{_{\mathrm{}}^{L/2}+_{L/2}^{\mathrm{}}\right\}dx\left(_\text{R}+_\text{L}\right)`$. While $`H_\text{E}`$ is not diagonal in the charged and neutral modes, their corresponding chemical potentials are still well–defined in the lead regions. As the densities in each of the four chiral edge–channel leads cannot change, chemical potentials remain constant as well Alekseev et al. (1998). Assuming again $`U\mathrm{}v_{\text{R/L}}^{(0)}`$, we find for these (in a compact notation where $`\mu _{i/j}`$ means $`\mu _i`$ or $`\mu _j`$, respectively)

$`\mu _\text{c}|_{x\stackrel{<}{>}\frac{L}{2}}`$ $`=`$ $`{\displaystyle \frac{\nu _\text{R}\mu _{1/2}\nu _\text{L}\mu _{4/3}}{\sqrt{|\nu _\text{R}\nu _\text{L}|}}}\text{sgn}(\nu _\text{R}\nu _\text{L}),`$ (11a)
$`\mu _\text{n}|_{x\stackrel{<}{>}\frac{L}{2}}`$ $`=`$ $`\sqrt{\stackrel{~}{\nu }}\left(\mu _{1/2}\mu _{4/3}\right)\text{sgn}(\nu _\text{R}\nu _\text{L}).`$ (11b)
Demanding continuity of $`\mu _{\text{c/n}}`$ at $`x=\pm L/2`$ yields four linear relations involving the chemical potentials in the four leads, the constants $`\overline{\varrho }_{\text{c/n}}`$, and $`I_\text{J}`$. After some straightforward algebra, we obtain the expressions

$`\mu _{2/4}`$ $`=`$ $`\mu _{1/3}\pm {\displaystyle \frac{2\pi \mathrm{}}{\nu _{\text{R/L}}}}I_\text{J},`$ (12a)
$`v_\text{c}\overline{\varrho }_\text{c}`$ $`=`$ $`{\displaystyle \frac{\nu _\text{R}\mu _1\nu _\text{L}\mu _3+2\pi \mathrm{}I_\text{J}}{2\pi \mathrm{}\sqrt{|\nu _\text{R}\nu _\text{L}|}}}\text{sgn}(\nu _\text{R}\nu _\text{L}),`$ (12b)
$`v_\text{n}\overline{\varrho }_\text{n}`$ $`=`$ $`{\displaystyle \frac{\mu _1\mu _3+\left(\frac{\pi \mathrm{}}{\nu _\text{R}}+\frac{\pi \mathrm{}}{\nu _\text{L}}\right)I_\text{J}}{2\pi \mathrm{}/\sqrt{\stackrel{~}{\nu }}}}\text{sgn}(\nu _\text{R}\nu _\text{L}),`$ (12c)
relating the ‘output’ chemical potentials $`\mu _{2/4}`$ as well as the constants $`\overline{\varrho }_{\text{c/n}}`$ to the experimentally adjustable ‘input’ chemical potentials $`\mu _{1/3}`$ and the a priori unknown current $`I_\text{J}`$ 222The result that external voltages enter as uniform constraints on chiral charge densities in the tunneling region is nontrivial. Similar relations arise for a homogeneous interacting quantum wire in the absence of backscattering. See, e.g., R. Egger and H. Grabert, Phys. Rev. B 58, 10761 (1998); I. Safi, Eur. Phys. J. B 12, 451 (1999).. To obtain the full solution for the transport problem of our finite QH junction that is attached to edge–channel leads, we are now left with the task to determine $`\overline{\varrho }_\text{n}`$ and $`I_\text{J}`$ self–consistently using the dynamics of the neutral mode expressed in Eqs. (3b), (6), (9b), and (12c). We now show how this can be achieved.

The Hamiltonian of the neutral mode \[given by Eq. (3b)\] is a realization of recently discussed Zülicke (1999); Naud et al. (2000) chiral sine–Gordon models. In contrast to the well–known nonchiral sine–Gordon model Tsvelik (1995), the quantum character of its dynamics arises because the bosonic field entering the cosine term does not commute with itself. Possible values of the parameter $`\stackrel{~}{\nu }`$ for the QH line junction discussed here can be parameterized by two non–negative integers $`m,m^{}`$ such that $`1/\stackrel{~}{\nu }=2|mm^{}|`$. These values correspond to QH junctions between systems having filling factors $`1/(2m+1)`$ and $`1/(2m^{}+1)`$, respectively. It has been shown Naud et al. (2000) that the cosine term constitutes only an irrelevant perturbation to the dynamics of the chiral bosonic field when $`|mm^{}|>2`$. More interesting, and easier to realize experimentally, are the two cases $`1/\stackrel{~}{\nu }\{2,4\}`$ where the cosine term turns out to be relevant or marginal, respectively, and exact solutions for its dynamics can be found Zülicke (1999); Naud et al. (2000).

Lets first consider the case $`\stackrel{~}{\nu }=1/2`$ realized, e.g., at a line junction between QH systems having filling factors $`1`$ and $`1/3`$, respectively. Introducing an auxiliary chiral boson field $`\eta (x)`$ that has the same chirality and velocity as $`\varphi _\text{n}`$, we can define fictitious chiral fermion operators $`\mathrm{\Psi }_/`$ via an inverse bosonization identity $`\mathrm{\Psi }_\sigma \mathrm{exp}\left\{i\text{sgn}(\nu _\text{R}\nu _\text{L})\left[\eta +\sigma \varphi _\text{n}\right]/\sqrt{2}\right\}`$. Note that the pseudospin degree of freedom indexed by $`\sigma `$ is not related to the spin of the original electrons in the sample. In the new fictitious–fermion degrees of freedom, Eqs. (3b) and (6) are quadratic:

$`_\text{n}^{}`$ $`=`$ $`{\displaystyle \underset{\sigma }{}}\mathrm{\Psi }_\sigma ^{}\left[i\text{sgn}(\nu _\text{R}\nu _\text{L})\mathrm{}v_\text{n}_x\right]\mathrm{\Psi }_\sigma `$ (13a)
$`+t\left(\mathrm{\Psi }_{}^{}\mathrm{\Psi }_{}e^{i\frac{x\mathrm{\Delta }}{\mathrm{}^2}\text{sgn}(\nu _\text{R}\nu _\text{L})}+\text{H.c.}\right),`$
$`_\text{J}^{}`$ $`=`$ $`i{\displaystyle \frac{t}{\mathrm{}}}\left(\mathrm{\Psi }_{}^{}\mathrm{\Psi }_{}e^{i\frac{x\mathrm{\Delta }}{\mathrm{}^2}\text{sgn}(\nu _\text{R}\nu _\text{L})}\text{H.c.}\right).`$ (13b)
In addition, density and chemical potential of the neutral mode are related to corresponding fictitious–fermion quantities via $`\mathrm{\Psi }_{}^{}\mathrm{\Psi }_{}\mathrm{\Psi }_{}^{}\mathrm{\Psi }_{}\sqrt{2}\varrho _\text{n}`$ and $`\mu _{}\mu _{}\sqrt{2}\mu _\text{n}`$. Note that only the pseudospin sector of the new fermionic theory has any bearing for real observations, while the pseudocharge sector described by the auxiliary field $`\eta `$ is hidden. We see that the problem of the original line junction between two strongly interacting edge branches with opposite chirality has been mapped onto that of tunneling between two branches of noninteracting and chiral fermions. The latter is readily solved using standard methods. For example, when tunneling is weak enough such that it is possible to neglect the contribution $`I_\text{J}`$ in Eq. (12c), we find $`e^2I_\text{J}=G_\text{J}(\mu _1\mu _3)`$ with the linear electric conductance

$$G_\text{J}=\frac{e^2}{2\pi \mathrm{}}\frac{\mathrm{sin}^2\left[\frac{\pi L}{L_t}\sqrt{1+\xi ^2}\right]}{1+\xi ^2}.$$
(14)
Here $`L_t=\pi \mathrm{}v_\text{n}/|t|`$ is a fundamental length scale set by tunneling, and $`\xi =\mathrm{}v_\text{n}\mathrm{\Delta }/(2|t|\mathrm{}^2)`$ a resonance parameter: $`G_\text{J}`$ is maximal for $`\xi 0`$ which corresponds to the resonance condition where both energy and 1D momentum are conserved in a tunneling event 333Note that the condition of weak tunneling used here is valid for $`G_\text{J}e^2/2\pi \mathrm{}`$, yet it does not restrict the tunneling strength to the perturbative limit $`LL_t`$.. The obtained linear dependence of $`I_\text{J}`$ on $`\mu _1\mu _3`$ has to be contrasted with the power law $`I_\text{J}(\mu _1\mu _3)^{\nu _\text{R}^1+\nu _\text{L}^11}`$ that is to be expected for momentum–resolved tunneling at a line junction between noninteracting chiral–Luttinger–liquid Wen (1992) edge channels. Furthermore, chirality of the effective tunneling problem described by Eqs. (13) results in charge oscillations along the junction similar to those predicted for QH bilayer systems Naud et al. (2000) and parallel quantum wires Boese et al. (2001).

Before concluding, we discuss the other nontrivial case $`\stackrel{~}{\nu }=1/4`$ which is realized, e.g., when $`\nu _\text{R}=1`$ and $`\nu _\text{L}=1/5`$. Again it is possible to solve the problem by refermionization Naud et al. (2000). Defining $`\psi _\text{n}(x)=\sqrt{z_\text{n}}_\text{n}\mathrm{exp}\{i\text{sgn}(\nu _\text{R}\nu _\text{L})\left[\varphi _\text{n}(x)+x\mathrm{\Delta }/2\mathrm{}^2\right]\}`$ and using the identity Naud et al. (2000) $`\psi _\text{n}(x)i_x\psi _\text{n}(x)=2\pi \text{sgn}(\nu _\text{R}\nu _\text{L})z_\text{n}^2_\text{n}^2\mathrm{exp}\{[2i\varphi _\text{n}(x)+ix\mathrm{\Delta }/\mathrm{}^2]\}`$, we can rewrite Eqs. (3b) and (6) as quadratic forms in the fictitious chiral Dirac fermion $`\psi _\text{n}`$. It turns out to be useful to utilize its decomposition in terms of Majorana fermions, $`\psi _\text{n}=(\chi _++i\chi _{})/\sqrt{2}`$, which yields

$`_\text{n}^{\prime \prime }`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{r=\pm }{}}\chi _r(i\mathrm{}v_r_x)\chi _r{\displaystyle \frac{\mathrm{}v_\text{n}\mathrm{\Delta }}{\mathrm{}^2}}i\chi _+\chi _{},`$ (15a)
$`_\text{J}^{\prime \prime }`$ $`=`$ $`{\displaystyle \frac{i\stackrel{~}{t}}{2\pi \mathrm{}}}\text{sgn}(\nu _\text{R}\nu _\text{L})\left(\chi _+_x\chi _{}+\chi _{}_x\chi _+\right),`$ (15b)
where $`v_\pm =\text{sgn}(\nu _\text{R}\nu _\text{L})\left[v_\text{n}\pm \stackrel{~}{t}/\pi \right]`$ with $`\stackrel{~}{t}=t\sqrt{z_\text{R}z_\text{L}}/z_\text{n}^2`$. The Hamiltonian $`_\text{n}^{\prime \prime }`$ is easily diagonalized, and the occupation–number distribution for Majorana fermions in reciprocal space is fixed by the requirement $`i\chi _+\chi _{}=\overline{\rho }_\text{n}`$. The transport problem can then be solved exactly again. A complete analysis is left to a later publication Zülicke and Shimshoni ; here we can only mention results for $`\mathrm{\Delta }=0`$ and in the limit of weak tunneling where it is possible to neglect the contribution proportional to $`I_\text{J}`$ in Eq. (12c). Quite different from the above considered case of $`\stackrel{~}{\nu }=1/2`$, we find here that $`I_\text{J}`$ is oscillating in time with period $`2(\pi \mathrm{})^2v_\text{n}/(\stackrel{~}{t}|\mu _1\mu _3|)`$. A similar dephasing effect as observed Ho (1994) in QH line junctions where $`\nu _\text{R}=\nu _\text{L}=1`$ leads to the temporal decay of the oscillation amplitude.

In summary, we have obtained exact solutions for transport through finite QH line junctions where the two edge channels belong to systems having different filling factors $`\nu _\text{R}`$ and $`\nu _\text{L}`$. Charging effects have been treated fully self–consistently by imposing appropriate boundary conditions for chemical potentials in the attached edge–channel leads. Strong coupling of edge channels via Coulomb interactions in a junction with $`\stackrel{~}{\nu }\frac{\nu _\text{R}\nu _\text{L}}{|\nu _\text{R}\nu _\text{L}|}=1/2`$ gives rise to a linear IV–characteristics for tunneling, as opposed to the power law expected in the absence of inter–edge correlations. At junctions with $`\stackrel{~}{\nu }=1/4`$, tunneling currents oscillate in time.

We thank N. Andrei, C. Chamon and V. Tripathi for useful discussions. This work was supported in part by the German Science Foundation (DFG) through Grant No. ZU 116/1 and the German Federal Ministry of Education and Research (BMBF) in the framework of the DIP program.