Inclusion Criteria:

- Serologic diagnosis of HIV infection as documented by a positive ELISA and confirmed
with a western blot, other federally approved HIV diagnostic test, or HIV viral load
measurement

- Biopsy-proven, measurable Kaposi's sarcoma with any of the following:

- Progressive cutaneous disease

- Symptomatic oropharyngeal or conjunctival lesions

- Any visceral involvement

- Tumor-related lymphedema

- Tumor-related ulceration or pain

- NOTE: All patients must have measurable disease; baseline measurements must be
obtained < 4 weeks prior to registration

- ECOG performance status 0-2

- ANC >= 1000/mm³ (with or without the use of colony-stimulating factors)

- Platelet count >= 50,000/mm³

- Hemoglobin >= 8 gm/dL

- Bilirubin < 1.5 x the upper limit of normal (unless elevation is due to Crixivan
administration with isolated elevation in conjugated bilirubin)

- SGOT or SGPT =< 5 x the upper limit of normal

- Creatinine =< 2.1 mg/dl

- Women must not be pregnant or lactating due to potential toxicity of therapy

- Women of childbearing potential and sexually active men must be advised to use an
accepted and effective method of contraception due to potential toxicity of therapy

- No prior systemic cytotoxic chemotherapy for Kaposi's sarcoma

- Prior radiation therapy must have been discontinued >= 7 days prior to randomization
and must NOT have been delivered to marker lesions; (NOTE: Radiation therapy will not
be permitted during study treatment)

- No active, untreated infection (no new opportunistic infectious complications within
the previous week requiring a change in antibiotics); maintenance therapy for
opportunistic infections will be allowed

- No prior or concomitant malignancy other than curatively treated carcinoma in situ of
the cervix or basal/squamous cell carcinoma of the skin

- No neuropsychiatric history or altered mental status that might prevent informed
consent or affect the ability of the patient to comply with the study

- Institutions must ask patients to participate in the quality of life portion of the
protocol; however, patients may decline participation in this component of the study
and still be eligible; the reason for refusal or inability to complete the QOL
assessments must be documented in the Assessment Compliance Form (#596)

- Must not be known to be sensitive to E. coli derived proteins

- No history of cardiac insufficiency (NY Heart Association status >= 2)

- Patients must be on stable (no change in drugs or doses) antiretroviral therapy for
greater than 14 days prior to study; a combination regimen is required; ideally this
will be a protease inhibitor containing triple therapy regimen

- Patients must give signed, written informed consent