Introducing the Motherboard

Feature Processor

Chipset
The motherboard uses a LGA775 socket that has the following features: Accommodates Intel P4/Celeron Processors Supports a system bus of 800/533MHz Supports Dual Core CPU Supports Hyper-Threading technology CPU Hyper-Threading technology enables the operating system into thinking its hooked up to two processors, allowing two threads to be run in parallel, both on separate logical processors within the same physical processor. The SiS649 Northbridge (NB) and SiS965 Southbridge (SB) chipset are based on an innovative and scalable architecture with proven reliability and performance. Supports 12 Outstanding Transactions and Quasi-SynchroSiS649 nous Host to DRAM timing (NB) Accommodates High Throughput SiS MuTIOL connecting to SiS965 MuTIOL media I/O with bi-directional 16-bit data bus to perform 1GB/s bandwidth in 133 MHz x 4 mode Supports PCI-Express X16 Graphic Port Supports DDR400/333/266 or DDR2-533/400 SDRAM Supports up to 2 unbuffered DDR2-533 DIMMs or 2 unbuffered DDR400 DIMMs up to 2 GB SiS965/965L Concurrent servicing of all DMA Devices: Dual IDE Controllers, SATA controller, three USB 1.1 host controllers and (SB) one USB 2.0 host controller, LAN MAC Controller and Audio/Modem DMA Controller Integrated MuTIOL 1G to PCI Express x1 Bridge, compliant with PCI Express 1.0a Compliant with PCI 2.3 specificaiton Compliant with Serial ATA 1.0 specification, supports up to four independent ports (SiS965 only) Compliant with AC97 v2.3 supporting 8 Channels of audio outputs and V.90 HSP-Modem Integrated USB 2.0/1.1 Controller sopporting up to eight USB ports Supports DDR up to 400/333/266 MHz SDRAM memory module Accommodates two DDR 184-pin un-buffered DIMM sockets Each slot supports up to 1GB with a total maximum capacity of 2GB

Memory

Expansion Options
The motherboard comes with the following expansion options. One PCI Express x16 slot Three 32-bit PCI slots Two IDE connectors which support four IDE channels A floppy disk drive interface The motherboard supports UltraDMA bus mastering with transfer rates of 133/100 66MB/s
1394a FireWire (optional)
Compliant Single Chip PCI Host Controller for IEEE1394-1995 Release 1.0 and IEEE 1394a-2000 Provides two 1394a fully compliant cable ports at 100/200/400 Mbit per second

* stands for optional components. This concludes Chapter 1. The next chapter explains how to install the motherboard.
Chapter 2 Installing the Motherboard Safety Precautions
Follow these safety precautions when installing the motherboard Wear a grounding strap attached to a grounded device to avoid damage from static electricity Discharge static electricity by touching the metal case of a safely grounded object before working on the motherboard Leave components in the static-proof bags they came in Hold all circuit boards by the edges. Do not bend circuit boards

Choosing a Computer Case

There are many types of computer cases on the market. The motherboard complies with the specifications for the Micro ATX system case. First, some features on the motherboard are implemented by cabling connectors on the motherboard to indicators and switches on the system case. Make sure that your case supports all the features required. Secondly, 649M2 supports one or two floppy diskette drives and four enhanced IDE drives. Make sure that your case has sufficient power and space for all drives that you intend to install. Most cases have a choice of I/O templates in the rear panel. Make sure that the I/O template in the case matches the I/O ports installed on the rear edge of the motherboard. This motherboard carries an Micro ATX form factor of 244 x 244 mm. Choose a case that accommodates this form factor.
Installing the Motherboard in a Case
Refer to the following illustration and instructions for installing the motherboard in a case. Most system cases have mounting brackets installed in the case, which correspond the holes in the motherboard. Place the motherboard over the mounting brackets and secure the motherboard onto the mounting brackets with screws. Ensure that your case has an I/O template that supports the I/O ports and expansion slots on your motherboard.
Installing the Motherboard
Do not over-tighten the screws as this can stress the motherboard.

Checking Jumper Settings

This section explains how to set jumpers for correct configuration of the motherboard.

Setting Jumpers

Use the motherboard jumpers to set system configuration options. Jumpers with more than one pin are numbered. When setting the jumpers, ensure that the jumper caps are placed on the correct pins. The illustrations show a 2-pin jumper. When the jumper cap is placed on both pins, the jumper is SHORT. If you remove the jumper cap, or place the jumper cap on just one pin, the jumper is OPEN. This illustration shows a 3-pin jumper. Pins 1 and 2 are SHORT
The following illustration shows the location of the motherboard jumpers. Pin 1 is labeled.

Jumper Settings

Jumper Type Description Setting (default) 1-2: CLEAR 2-3: NORMAL CLR_CMOS 3-pin CLEAR CMOS Before clearing the CMOS, make sure to turn off the system. Clear CMOS 1

BIOS_WP 2-pin BIOS Protect

Open: Short:

Disable Enable

BIOS_WP

Connecting Case Components
After you have installed the motherboard into a case, you can begin connecting the motherboard components. Refer to the following: Connect the CPU cooling fan cable to CPU_FAN. Connect the power cooling fan connector to PWR_FAN.(optional) Connect the system cooling fan connector to SYS_FAN. Connect the case switches and indicator LEDs to the PANEL1. If there is a 3pin LED cable, connect it to SJ1.(optional) Connect the standard power supply connector to ATX_POWER. Connect the auxiliary case power supply connector to ATX12V.
Connecting 20/24-pin power cable
Users please note that the 20-pin and 24-pin power cables can both be connected to the ATX_POWER connector. With the 20-pin power cable, just align the 20-pin power cable with the pin 1 of the ATX_POWER connector. However, using 20-pin power cable may cause the system to become unbootable or unstable because of insufficient electricity. The minimum recommend power is 300W for a fully-configured system. With ATX v1.x power supply, users please note that when installing 20-pin power cable, the latche of power cable falls on the left side of the ATX_POWER connector latch, just as the picture shows. 20-pin power cable
With ATX v2.x power supply, users please note that when installing 24-pin power cable, the latches of power cable and the ATX_POWER match perfectly. 24-pin power cable
CPU_FAN: CPU Cooling Fan Connector

Signal Name GND +12V

Function
System Ground Power +12V Sensor FAN Control Signal

Control

Users please note that the fan connector supports the CPU cooling fan of 1.1A~2.2 (26.4W max.) at +12V.
SYS_FAN/PWR_FAN: FAN Power Connectors
Pin Signal Name GND +12V Function
System Ground Power +12V Sensor
ATX12V: ATX 12V Power Connector
Pin Signal Name Ground Ground +12V +12V
ATX_PWR: ATX 24-pin Power Connector
Pin Signal Name +3.3V +3.3V Ground +5V Ground +5V Ground PWRGD +5VSB +12V +12V +3.3V Pin Signal Name +3.3V -12V COM PS_ON COM COM COM -5V +5V +5V +5V COM

SJ1: Single-color LED header (optional)

1 Pin 2 3

Signal Name ACPI Name Signal LED ACPI LED 5VSB

ACPI LED function

S0 Light S1 Blinking S3 Blinking S4/S5 Dark

Front Panel Header

The front panel header (PANEL1) provides a standard set of switch and LED headers commonly found on ATX or Micro ATX cases. Refer to the table below for information:

Signal

Pin 6 8
HD_LED_P Hard disk LED(+) HD_LED_N Hard disk LED(-) RST_SW_N Reset Switch(-) RST_SW_P RSVD Reset Switch(+) Reserved
FP PWR/SLP *MSG LED(+) FP PWR/SLP *MSG LED(-) PWR_SW_P Power Switch(+) PWR_SW_N Power Switch(-) No pin

10 Key

* MSG LED (dual color or single color)

Hard Drive Activity LED

Connecting pins 1 and 3 to a front panel mounted LED provides visual indication that data is being read from or written to the hard drive. For the LED to function properly, an IDE drive should be connected to the onboard IDE interface. The LED will also show activity for devices connected to the SCSI (hard drive activity LED) connector.
Power/Sleep/Message waiting LED
Connecting pins 2 and 4 to a single or dual-color, front panel mounted LED provides power on/off, sleep, and message waiting indication.

Reset Switch

Supporting the reset function requires connecting pin 5 and 7 to a momentary-contact switch that is normally open. When the switch is closed, the board resets and runs POST.

Power Switch

Supporting the power on/off function requires connecting pins 6 and 8 to a momentarycontact switch that is normally open. The switch should maintain contact for at least 50 ms to signal the power supply to switch on or off. The time requirement is due to internal debounce circuitry. After receiving a power on/off signal, at least two seconds elapses before the power supply recognizes another on/off signal.

Installing Hardware

Installing the Processor
Caution: When installing a CPU heatsink and cooling fan make sure that you DO NOT scratch the motherboard or any of the surface-mount resistors with the clip of the cooling fan. If the clip of the cooling fan scrapes across the motherboard, you may cause serious damage to the motherboard or its components. On most motherboards, there are small surface-mount resistors near the processor socket, which may be damaged if the cooling fan is carelessly installed. Avoid using cooling fans with sharp edges on the fan casing and the clips. Also, install the cooling fan in a well-lit work area so that you can clearly see the motherboard and processor socket.

Before installing the Processor
This motherboard automatically determines the CPU clock frequency and system bus frequency for the processor. You may be able to change these settings by making changes to jumpers on the motherboard, or changing the settings in the system Setup Utility. We strongly recommend that you do not over-clock processors or other components to run faster than their rated speed.
Warning: Over-clocking components can adversely affect the reliability of the system and introduce errors into your system. Over-clocking can permanently damage the motherboard by generating excess heat in components that are run beyond the rated limits. This motherboard has a LGA775 processor socket. When choosing a processor, consider the performance requirements of the system. Performance is based on the processor design, the clock speed and system bus frequency of the processor, and the quantity of internal cache memory and external cache memory.
CPU Installation Procedure
The following illustration shows CPU installation components. A. Unload the cap Use thumb & forefinger to hold the lifting tab of the cap. Lift the cap up and remove the cap completely from the socket. B. Open the load plate Use thumb & forefinger to hold the hook of the lever, pushing down and pulling aside unlock it. Lift up the lever. Use thumb to open the load plate. Be careful not to touch the contacts. C. Install the CPU on the socket Orientate CPU package to the socket. Make sure you match triangle marker to pin 1 location. D. Close the load plate Slightly push down the load plate onto the tongue side, and hook the lever. CPU is locked completely. E. Apply thermal grease on top of the CPU. F. Fasten the cooling fan supporting base onto the CPU socket on the motherboard.
G. Make sure the CPU fan is plugged to the CPU fan connector. Please refer to the CPU cooling fan users manual for more detail installation procedure.
To achieve better airflow rates and heat dissipation, we suggest that you use a high quality fan with 3800 rpm at least. CPU fan and heatsink installation procedures may vary with the type of CPU fan/heatsink supplied. The form and size of fan/heatsink may also vary.

About SATA Connectors

This motherboard features four SATA connectors supporting a total of four drives. SATA refers to Serial ATA (Advanced Technology Attachment) is the standard interface for the IDE hard drives which are currently used in most PCs. These connectors are well designed and will only fit in one orientation. Locate the SATA connectors on the motherboard (see page 20) and follow the illustration below to install the SATA hard drives.
Installing Serial ATA Hard Drives
To install the Serial ATA (SATA) hard drives, use the SATA cable that supports the Serial ATA protocol. This SATA cable comes with an SATA power cable. You can connect either end of the SATA cable to the SATA hard drive or the connector on the motherboard.

SATA cable

(optional)

SATA power cable

Refer to 3
the illustration below for proper installation: Attach either cable end to the connector on the motherboard. Attach the other cable end to the SATA hard drive. Attach the SATA power cable to the SATA hard drive and connect the other end to the power supply.
This motherboard does not support the Hot-Plug function.
Installing a Floppy Diskette Drive
The motherboard has a floppy diskette drive (FDD) interface and ships with a diskette drive ribbon cable that supports one or two floppy diskette drives. You can install a 5.25-inch drive and a 3.5-inch drive with various capacities. The floppy diskette drive cable has one type of connector for a 5.25-inch drive and another type of connector for a 3.5-inch drive. You must orient the cable connector so that the pin 1 (color) edge of the cable corresponds to the pin 1 of the I/O port connector.
FDD: Floppy Disk Connector
This connector supports the provided floppy drive ribbon cable. After connecting the single end to the onboard floppy connector, connect the remaining plugs on the other end to the floppy drives correspondingly.

Installing Add-on Cards

The slots on this motherboard are designed to hold expansion cards and connect them to the system bus. Expansion slots are a means of adding or enhancing the motherboards features and capabilities. With these efficient facilities, you can increase the motherboards capabilities by adding hardware that performs tasks that are not part of the basic system.

PCIEx16 Slot

The PCI Express x16 slot is used to install an external PCI Express graphics card that is fully compliant to the PCI Express Base Specification revision 1.0a. This motherboard is equipped with two standard PCI slots. PCI stands for Peripheral Component Interconnect and is a bus standard for expansion cards, which for the most part, is a supplement of the older ISA bus standard. The PCI slots on this board are PCI v2.3 compliant. Before installing an add-on card, check the documentation for the card carefully. If the card is not Plug and Play, you may have to manually configure the card before installation.

PCI1~3 Slots

Follow these instructions to install an add-on card: 3 Remove a blanking plate from the system case corresponding to the slot you are going to use. Install the edge connector of the add-on card into the expansion slot. Ensure that the edge connector is correctly seated in the slot. Secure the metal bracket of the card to the system case with a screw.
For some add-on cards, for example graphics adapters and network adapters, you have to install drivers and software before you can begin using the add-on card.
Connecting Optional Devices
Refer to the following for information on connecting the motherboards optional devices:
SPDIFO1: SPDIF out header
This is an optional header that provides an S/PDIF (Sony/Philips Digital Interface) output to digital multimedia device through optical fiber or coaxial connector.
Pin Signal Name SPDIF +5VA Key GND Function
SPDIF digital output 5V analog Power No pin Ground
AUDIO1: Front Panel Audio header
This header allows the user to install auxiliary front-oriented microphone and line-out ports for easier access.
Pin Signal Name Pin Signal Name AUD_MIC AUD_GND AUD_VCC AUD_F_R AUD_RET_R REVD Key AUD_F_L AUD_RET_L Function Front Panel Microphone input signal Ground used by Analog Audio Circuits Filtered +5V used by Analog Audio Circuits Right Channel audio signal to Front Panel RightChannelAudiosignaltoReturnfromFrontPanel Reserved No Pin Left Channel Audio signal to Front Panel Left Channel Audio signal to Return from Front Panel
AUD_MIC_BIAS Microphone Power
CD_IN: Analog audio input connector
Pin Signal Name CD in_L GND GND CD in_R Function
CD In left channel Ground Ground CD In right channel
SATA1~SATA4: Serial ATA connectors
These connectors are use to support the new Serial ATA devices for the highest date transfer rates (150 MB/s), simpler disk drive cabling and easier PC assembly. It eliminates limitations of the current Parallel ATA interface. But maintains register compatibility and software compatibility with Parallel ATA.
Pin Signal Name Ground TXRXGround Pin Signal Name TX+ Ground RX+ -
Users please note that SiS965L supports 2 Serial ATA conenctors only.

When you start the Setup Utility, the main menu appears. The main menu of the Setup Utility displays a list of the options that are available. A highlight indicates which option is currently selected. Use the cursor arrow keys to move the highlight to other options. When an option is highlighted, execute the option by pressing <Enter>. Some options lead to pop-up dialog boxes that prompt you to verify that you wish to execute that option. Other options lead to dialog boxes that prompt you for information. Some options (marked with a triangle ) lead to submenus that enable you to change the values for the option. Use the cursor arrow keys to scroll through the items in the submenu. In this manual, default values are enclosed in parenthesis. Submenu items are denoted by a triangle.

Standard CMOS Features

This option displays basic information about your system.
Phoenix-AwardBIOS CMOS Setup Utility Standard CMOS Features Date (mm:dd:yy) Wed, Jan Time (hh:mm:ss) 9 : 33 : 26 IDE Channel 0 Master IDE Channel 0 Slave IDE Channel 1 Master IDE Channel 1 Slave IDE Channel 2 Master IDE Channel 2 Slave IDE Channel 3 Master IDE Channel 3 Slave Drive A Drive B Floppy 3 Mode Support Video Halt On Base Memory Extended Memory Total Memory [1.44M, 3.5 in.] [None] [Disabled] [EGA/VGA] [All Errors] 640K 65535K 1024K Item Help Menu Level Change the day, month, year and century
: Move Enter: Select +/-/PU/PD:Value F10:Save ESC:Exit F1: General Help F5:Previous Values F6:Fail-Safe Defaults F7:Optimized Defaults
Date and Time The Date and Time items show the current date and time on the computer. If you are running a Windows OS, these items are automatically updated whenever you make changes to the Windows Date and Time Properties utility. IDE Devices (None) Your computer has two IDE channels (Primary and Secondary) and each channel can be installed with one or two devices (Master and Slave). Use these items to configure each device on the IDE channel. This motherboard features four SATA connectors supporting four SATA drives. SATA refers to Serial ATA (Advanced Technology Attachment), the standard interface for the IDE hard drives which are currently used in most PCs.

Advanced Chipset Features
These items define critical timing parameters of the motherboard. You should leave the items on this page at their default values unless you are very familiar with the technical specifications of your system hardware. If you change the values incorrectly, you may introduce fatal errors or recurring instability into your system.
Phoenix-AwardBIOS CMOS Setup Utility Advanced Chipset Features DRAM Clock/Drive Control [Press Enter] System BIOS Cacheable [Disabled] Video RAM Cacheable [Disabled] Item Help Menu Level
DRAM Clock/Drive Control (Press Enter)
Phoenix-AwardBIOS CMOS Setup Utility DRAM Clock/Timing Control DDR CAS Latency DRAM Timing Control x RAS to CAS Delay (tRCD) x Precharge Time (tRP) x RAS Active Time (tRAS) x Write Recovery Time (tWR) Command Bypass Data Bypass UMC0 MA Timing UMC0 Read Data Ready [By SPD] [Auto] 2T 2T 15T 1T [Disabled] [Disabled] [Auto] [Auto] Item Help Menu Level
DDR CAS Latency (SPD) This item controls the timing delay (in clock cycles) before the DRAM starts a read command after receiving it. DRAM Timing Control (Auto) Enables you to select the CAS latency time in HCLKs of 2, 2.5, or 3. The value is set at the factory depending on the DRAM installed. Do not change the values in this field unless you change specifications of the installed DRAM or the installed CPU. RAS to CAS Delay (tRCD) (2T): This is the amount of time a CAS is performed after a RAS. The lower the better, but some DRAM does not support low figures.
Precharge Time (tRP) (2T): This is the duration of the time interval during which the Row Address Strobe signal to a DRAM is held low during normal Read and Write Cycles. This is the minimum interval between completing one read or write and starting another from the same (non-page mode) DRAM. Techniques such as memory interleaving, or use of Page Mode DRAM are often used to avoid this delay. Some chipsets require this parameter in order to set up the memory configuration properly. The RAS Precharge value is typically about the same as the RAM Access (data read/write) time. RAS Active Time (tRAS) (15T) : This item allows you to set the amount of time a RAS can be kept open for multiple accesses. High figures will improve performance. Write Recovery Time (tWR)(1T): This item defines DRAM internal write to read command delay in the same device. Command Bypass(Disabled) When enabled, request will bypass the command queue if the queue is empty. Data Bypass (Disabled) When enabled, the latency of read data from DRAM back to CPU will be lower. UMC0 MA Timing (Auto) This option allows you to set the lead off DRAM read and write cycles. When set to Delay 1T, memory read/write commands are sent one clock cycle behind the memory address. When set to Normal, read/write and memory address commands are sent simultaneously. UMC0 Read Data Ready (Auto) This item defines the channel A DRAM read data latency. Press <Esc> to return to the Advanced Chipset Features page. System BIOS Cacheable (Disabled) This item allows the system to be cached in memory for faster execution. Enable this item for better performance. Video RAM Cacheable (Disabled) These items allow the video BIOS and RAM to be cached in memory for faster execution. Enable these items for better performance.

PM Wake Up Events (Press Enter)
Phoenix-AwardBIOS CMOS Setup Utility PM Wake Up Events IRQ [3-7, 9-15], NMI IRQ 8 Break Suspend Resume By WOL/WOM/RING Resume By MACPME Resume By PCI PME Resume By USB (S3) PS2 KB Wakeup from S3 PS2 MS Wakeup from S3 Month Alarm Day of Month Alarm Time (hh:mm:ss) Alarm **Reload Global Timer Events** Primary IDE Secondary IDE FDD, COM, LPT Port PCI PIRQ[A-D]# [Enabled] [Disabled] [Disabled] [Enabled] [Enabled] [Disabled] Item Help Menu Level
Na : 0 : 0 [Disabled] [Disabled] [Disabled] [Disabled]
IRQ [3-7, 9-15], NMI (Enabled) This option determines whether any activity for IRQ 3-7/9-15 will cause the system to wake from a power saving mode. IRQ 8 Break Suspend (Disabled) Determines whether the system will monitor IRQ 8 activity and wake the system from a power saving mode when IRQ 8 is activated. Resume By WOL/WOM/RING (Disabled) Use this item to enable LAN or modem activity to wakeup the system from a power saving mode.
Resume By MACPME (Enabled) Use this item to enable MAC activity to wake up the system from a power saving mode. Resume By PCI PME (Enabled) This item allows users to enable or disable PCI activity to wakeup the system from a power saving mode. Resume By USB (S3) (Disabled) This item allows users to enable or disable USB activity to wakeup the system from a power saving mode. PS2 KB/MS Wakeup from S3 (Disabled) This option enables or disables you to allow mouse or keyboard activity to awaken the system from power saving mode. ** Reload Global Timer Events ** Global Timer (power management) events are I/O events whose occurrence can prevent the system from entering a power saving mode or can awaken the system from such a mode. In effect, the system remains alert for anything that occurs to a device that is configured as Enabled, even when the system is in a power-down mode. Primary/Secondary IDE 1/0 (Disabled) When these items are enabled, the system will restart the power-saving timeout counters when any activity is detected on any of the drives or devices on the primary or secondary IDE channels. FDD, COM, LPT Port (Disabled) When this item is enabled, the system will restart the power-saving timeout counters when any activity is detected on the floppy disk drive, serial ports, or the parallel port. PCI PIRQ[A-D]# (Disabled) When disabled, any PCI device set as the Master will not power on the system. Press <Esc> to return to Power Management Setup page.

Assign IRQ For USB (Enabled) Names the interrupt request (IRQ) line assigned to the USB on your system. Activity of the selected IRQ always awakens the system. Maximum ASPM supported (L0s&L1) This item controls the maximum level of ASPM supported on the given PCI Express links on the system. Maximum Payload Size (4096) This item specifies the maximum TLP payload size for the PCI Express devices. The unit is byte. INT Pin 1-8 Assignment (Auto) Identifies the interrupt request (IRQ) line assigned to a device connected to the PCI interface of your system.

PC Health Status

On motherboards that support hardware monitoring, this item lets you monitor the parameters for critical voltages, temperatures and fan speeds.
Phoenix-AwardBIOS CMOS Setup Utility PC Health Status Shutdown Temperature Warning Temperature CPU Core Voltage DDR Voltage Vcc 3.3V Vcc 5.0V +12V Voltage Battery CPU Temperature System Temperature CPU FAN Speed SYS FAN Speed PWR FAN Speed [Disabled] [Disabled] Item Help Menu Level
Shutdown Temperature (Disabled) Enables you to set the maximum temperature the system can reach before powering down. Warning Temperature (Disabled) This item allows users to set the CPU warning temperature. The default setting is Disabled. Users may change it to 60C/140F, 65C/149F, 70C/158F, 75C/167F, or 80C/176F System Component Characteristics These fields provide you with information about the systems current operating status. You cannot make changes to these fields. CPU Core Voltage DDR Voltage 3.3V 5.0V 12V Voltage Battery CPU Temperature System Temperature CPU FAN Speed SYS FAN Speed PWR FAN Speed
Frequency/Voltage Control
This item enables you to set the clock speed and system bus for your system. The clock speed and system bus are determined by the kind of processor you have installed in your system.
Phoenix-AwardBIOS CMOS Setup Utility Frequency/Voltage Control CPU Clock Ratio [ 0 X] Auto Detect PCI Clk [Enabled] Spread Spectrum [Enabled] Colck Control By [Auto] x Async PCI Clock control Disabled x CPU Clock 100 x CPU:DRAM Frequency Ratio SPD DRAM Frequency Item Help Menu Level
CPU Clock Ratio (0 X) Use the CPU Host/SDRAM/PCI Clock to set the frontside bus frequency for the installed processor (usually 133 MHz, 100 MHz or 66 MHz). Then use CPU Clock Ratio Jumpless to set a multiple. The multiple times the frontside bus must equal the core speed of the installed processor e.g., 3.5 (multiple) x 100 MHz (frontside bus) = 350 MHz (installed processor clock speed). Auto Detect DIMM/PCI Clk (Enabled) When this item is enabled, BIOS will disable the clock signal of free DIMM/PCI slots. Spread Spectrum (Enabled) If you enable spread spectrum, it can significantly reduce the EMI (Electro-Magnetic Interference) generated by the system. Clock Control By (Auto) Use this item to set the CPU Host Clock frequency to Auto or by manual setting. Select Manual to activate the following items and set each item manually. Async PCI Clock control (Disabled): This item allows you to select the fixed clock to generate the output to PCI frequency. CPU Clock (100): Use the CPU Host Clock to set the fronside bus frequency for the installed processor (usually 200MHz, 133 MHz or 100 MHz). CPU:DRAM Frequency Ratio (SPD): This item determines if the DRAM frequency is controlled by SPD or by manually. Do not change the value in this field unless you know the specification of the installed DRAM orthe installed CPU quite well.

Creating a RAID 0+1 (Stripe-Mirror) Array
Only SiS965 controller can support RAID 0+1 function The selection of RAID 0+1 will appear when 4 single HDD existing. For users convenience, RAID 0+1 will be auto created. For best performance, the sequence of RAID 0+1 is forced to set as Disk1-> Disk 3-> Disk 2-> Disk 4. Press <A> to start creating a RAID array. Press <4> and <Enter> to select RAID 0+1.
To create an a Stripe-Mirror array, follow these steps:
After step 2, RAID 0+1 array will be shown on the top of the main frame.
Press <Q> until exit this BIOS utility RAUID Setup menu and the red message frame will show as the same as the creation of the RAID 0 array. Press <Y> and <Enter> to save changes.
Once the array has been created, you will need to FDUSK and FORMAT the array as if it were a new single hard drive.

Creating a JBOD Array

SiS965 enables users to create a JBOD array with 2, 3, or 4 drives. SiS965L enables users to create a JBOD array with 2 drives.
To create an JBOD array, follow these steps:
Press <A> to start creating a RAID array. Press <1> and <Enter> to select JBOD. You will have two selections to create a JBOD array. The default value is <1>. If you select <1>Auto Create, you can create a JBOD array faster and easier. The result after creating will be show on step 5. Besides, you also can select <2>Manual Create, see following steps.
Use <> < > to select disk, and press <Enter> to select disk, <Q> to exit. When you press <Enter> on the disk you wanted, the RAID Type will be changed from Single to JBOD.
After all steps finished, press <Q> until escape the setup menu and JBOD array will be show on the top of the main frame.
Press <Q> again to exit this BIOS utility and the red message frame will show as the same age as the creation of the RAID 0 array. Press <Y> and <Enter> to save changes. Once the array has been created, you will need to FDISK and format the array as if it were a new single hard drive.
This concludes Chapter 5.
La carte mre utilise un socket LGA775 ayant les caractristiques suivantes : Reoit des processeurs Intel P4/Celeron Support un bus systme (FSB) de 800/533 MHz Prend en charge les CPU double noyau Supporte le CPU de technologie Hyper-Threading La technologie Hyper-Threading permet au systme dexploitation de penser quil est connect deux processeurs, permettant dexcuter deux threads en parallle, la fois sur des processeurs logiques dans le mme processeur physique.
La SiS 649 Northbridge (NB) et SiS965 Southbridge (SB) sont bass sur une architecture novatrice et dimensionnable avec une abilit et des performances prouves.

The Online Median Problem
Ramgopal R. Mettu November 1999

C. Greg Plaxton

Abstract We introduce a natural variant of the (metric uncapacitated) -median problem that we call the online median problem. Whereas the -median problem involves optimizing the simultaneous placement of facilities, the online median problem imposes the following additional constraints: the facilities are placed one at a time; a facility, once placed, cannot be moved; the total number of facilities to be placed, , is not known in advance. The objective of an online median algorithm is to minimize competitive ratio, that is, the worst-case ratio of the cost of an online placement to that of an optimal ofine placement. Our main result is a linear-time constant-competitive algorithm for the online median problem. In addition, we present a related, though substantially simpler, linear-time constant-factor approximation algorithm for the (metric uncapacitated) facility location problem. The latter algorithm is similar in spirit to the recent primal-dual-based facility location algorithm of Jain and Vazirani, but our approach is more elementary and yields an improved running time.
Department of Computer Science, University of Texas at Austin, Austin, TX 78712. This research was supported by NSF Grant CCR9821053. Email: ramgopal, plaxton @cs.utexas.edu.

1 Introduction

Recently the rst constant-factor approximation algorithm was discovered for the -median problem by Charikar et al. [3]; in this paper, we ask whether a constant competitive ratio can be achieved for a natural online extension of the -median problem. Let be a nonempty set of points and let be a metric distance function on. The -median problem is concerned with marking points such that the sum over all points of the weight of times the distance from to the closest marked point is minimized. For the online , the rst points median problem, we wish to nd an ordering of the points such that for all , provide a good solution (e.g. constant factor approximation) to the -median problem. An obvious approach to the online median problem is to iteratively choose the point that minimizes the objective function. Greedy strategies of this kind are commonly applied in the design of online algorithms [1, 9]. It turns out, however, that for the online median problem, the simple strategy suggested above has an unbounded competitive ratio. We show that a modication of this strategy that we call hierarchically greedy can be used to obtain a constant-competitive linear-time algorithm for the online median problem. We develop this strategy by rst considering a simple greedy algorithm for facility location.

1.1 Problem Denitions

Without loss of generality, throughout this paper we consider a xed set of points with an associated and nonnegative functions. We are primarily interested distance function in the case where the function is a metric, that is, where is nonnegative, symmetric, satises the triangle iff. For the online median problem, it will prove to be useful to consider a inequality, and slightly more general class of distance functions in which the triangle inequality is relaxed to the following : For any sequence of points in , -approximate triangle inequality, where. We refer to such a distance function as a -approximate metric. We let , and dene a subset of to be a conguration iff it is nonempty. For any point and conguration , we dene as. We consider three computational problems: -median, online median, and facility location. For the -median and online median problems, the cost of a conguration, denoted , is dened to be. The input to the -median problem is , , and an integer ,. and The output is a minimum-cost conguration of size. The input to the online median problem is. The output is a total order on. We dene the competitive ratio of such an ordering as the maximum over all , , of the ratio of the cost of the conguration given by the rst points in the ordering to that of an optimal -median conguration. We dene the competitive ratio of an online median algorithm and , of the competitive ratio of the as the supremum, over all possible choices of the input instance ordering produced by the algorithm. , is dened as the sum of For the facility location problem, the cost of a conguration, denoted and. The input to the facility location problem is , , and. The output is a minimum-cost conguration.

1.2 Previous Work

There has been much prior work on the facility location and -median problems; here we focus on the work that is most relevant to our results. The rst constant-factor approximation algorithm for facility location is due to Shmoys et al. [17] and is based on rounding the (fractional) solution to a linear program. Chudak [4] gives an LP-based -approximation algorithm for facility location. This was the best constant factor known until the recent work of Charikar and Guha [2], which establishes a slightly lower approximation ratio of. The rst constant-factor approximation for the -median problem was recently given by 1
s irqph i @ S 5 A8 T 0 I RQQQS 0PPP I

T3d5 ihgf

) T3ed0

us`

8us` 5 2
( 4" "31) & $ 20

2 93ed0

G E HFD

8 jlut W 5 2U 8 s 5

7C@ BA@( '%#" & $ !
8 utuW 5 2U 8 s 5 5 eyxv utw 8 s gedS cb9`I XVD f a a 5 aY WUD

8pon mG X1t5

Vhx

sn P trqG

8 k) j W 5
Charikar et al. [3] and is also LP-based. That work follows a sequence of bicriteria results utilizing LPbased techniques [14, 15]. Jain and Vazirani [10] give the rst nearly linear-time combinatorial algorithms for the facility location and -median problems, achieving approximation ratios of and , respectively. While the latter algorithms are combinatorial, the primal-dual approach used in their analysis is based on linear programming theory. (See [6] for an excellent introduction to the primal-dual method.) Strategies based on local search and greedy techniques for facility location and the -median problem have been previously studied. The work of Korupolu et al. [11] shows that a simple local search heuristic proposed Kuehn and Hamburger [13] yields both a constant-factor approximation for the facility location problem and a bicriteria approximation for the -median problem [11]. Guha and Khuller [7] showed that greedy improvement can be used as a postprocessing step to improve the approximation guarantee of certain facility location algorithms. Guha and Khuller also provide the best lower bound known of on the approximation ratio for this problem. More recently, Charikar and Guha [2] achieved the best approximation ratio known for facility location by combining a local search heuristic with the best LP-based algorithm known. Charikar and Guha also give a -approximation for the -median problem by building on the techniques of Jain and Vazirani [10]. To the best of our knowledge, the online median problem has not been previously studied. Note that any constant-competitive algorithm for the online median problem is also a constant-factor approximation algorithm for the -median problem, but the converse does not hold. In particular, constant-factor approximation algorithms for the -median problem known prior to this work [2, 3, 10] seem to rely heavily on the knowledge of. As such it is unclear whether any of these algorithms can be easily modied to obtain a constant-competitive online median algorithm.

1.3 Contributions

Algorithms for problems in discrete location theory arise in many practical applications; see [5, 16], for example, for numerous pointers to the literature. Given that many of these problems are NP-hard, it is desirable to develop fast approximation algorithms. As mentioned above, it is not uncommon for approximation algorithms to be based on a greedy approach. In this paper, we show that greedy strategies yield a fast constant-factor approximation algorithm for the facility location problem and a fast constant-competitive algorithm for the online median problem. We give a linear-time algorithm for the facility location problem that achieves an approximation ratio of. The main idea of the algorithm is to compute and use the value of balls about every point in the metric space. In retrospect, the idea of value is implicit in the work of Jain and Vazirani [10]. We make this idea explicit and use the values of balls to make greedy choices. Additionally, our algorithm is faster than the Jain-Vazirani algorithm by a logarithmic factor. While a simple greedy algorithm yields a constant-factor approximation bound for the facility location problem, it appears that a more sophisticated approach is needed to obtain a constant-factor approximation guarantee for the -median problem, let alone a constant-competitiveness result for the online median problem. For example, in Section 3 we show that perhaps the most natural greedy approach to the -median (resp., online median) problem leads to an unbounded approximation (resp., competitive) ratio. Our main result is a linear-time constant competitive algorithm for the online median problem. We achieve this result using a hierarchically greedy approach. The basic idea behind this approach is as follows: Rather than selecting a point based on a single greedy criterion, we greedily choose a region (the set of points lying within some ball) and then recursively select a point within that region. Thus, the choice of point is inuenced by a sequence of greedy criteria addressing successively ner levels of granularity.

uv P txqwG

1.4 Outline
The rest of this paper is organized as follows. In Section 2, we present our facility location algorithm and prove that it achieves a constant approximation ratio. In Section 3, we present our online median algorithm and prove that it is constant-competitive. Section 4 offers some concluding remarks.

2 Facility Location

The following denitions are used throughout the present section as well as Section 3.
Given a ball , we let denote the set. However, for. For example, we write and the sake of brevity, we tend to write instead of instead of and , respectively. The value of a ball

, denoted

For any ball
and any nonnegative real , we dene

as the ball

2.1 Algorithm
In the rst step of the following algorithm, we assume for the sake of convenience that there is at least one point such that. (The problem is trivial otherwise.) The output of the algorithm is the conguration , which we also refer to as. Remark: The indexing of the sets has been introduced solely to facilitate the analysis. For each point , determine an associated ball

such that

Determine a bijection Let

such that ,

denote the ball : If

then let

; otherwise, let
We now sketch a simple linear-time implementation of the above algorithm. For each point , the associated radius can be computed in time. (This is essentially a weighted selection problem.) Thus the rst step requires time. The second step involves sorting values and can be accomplished in time. The running time for the third step is negligible. Each iteration of the fourth step can be easily implemented in time, for a total of time.

2.2 Approximation Ratio

In this section we establish the following theorem.
Proof: Immediate from Lemmas 2.3 and 2.7 below.

U u usQxAdQ s

Theorem 1 For any conguration
f a a h@ geda } f C@ a n Ta a h@ geda C@ I Af ea f ff a Rf 1ca R $| { 8 kCk5 ) @ 30 @ 5
A ball is a pair of , denoted
@ x30 C 675RUtW 5 @ x30 C 8 rxc F5xc6c 8xc f R5xc6c 87 i 7} 8 5xc6c 830 i 5 @ 8cXt 30 5
, where the center of , denoted , is a nonnegative real. , belongs to

85d6Q z i l~R}

| ` {z

GfV B @ 8 a @ a a 5

y y y y y y y y y
For any nonnegative integer , let

denote the set

, and the radius
tRxv } 5 n m Vj6A0 a 6j8 a 5 a 5 a m Q a a t E 8 s 5 a ut0 Q a f r fr an a 8 s @ a 5 tCls 9 a s 5 U u ut0 t0 Q s n B@ f 5 E 0 6u6fAa 5 } v U n a 65a f0 30 a RxA
be a point and let and conguration belong to ,. If in does not belong to such that and belongs to. , then.
0 Q a 6 a Q a 0 @ 5 8 6%V f a 6 a f0 Q a 8 a 0 6fE B8 a 0 6t@ 5 m8 a E8t0 s 5 E 8 s 5 9 a a 6 a gF8 a ut0 Q t8 a R1xft} v E 8 s 8tHs s @ a 5 s 9 a a a kC8 a 6r 5 ) @ 5 sQ` 2U 8 s 38 Rt 18 a 9 @ m 5 t t 8 jut8 t6 6u a 5 8 ut0 t 5 2U 8 s 5 m 5 2U 8 a 5 @ 5 2U 8 s 5
does not belong to be a point and let be a point, let since. be a conguration, and let , then. , belong to. If. belongs to belong to and. , then belongs to. Otherwise,. If.
@ 5 2U 8 s 5 sQ`k8 t0 Q W s P Xta 5 a 3R1xv 4gutt0 } m8 s @ 8 s s
, let. Thus. Furthermore, since

a f a n E a 30 a R} xjf vU n a 5 fx a n a a 9 n a a f
, then. Then in such that is empty, and so and belongs to.
Proof: The claim is immediate unless there is a point exists, then Lemmas 2.2 and 2.5 imply The claim now follows since
Proof: By Lemma 2.2, there is no point in such that follows from the denition of , since
Proof: Let be some point in such that. By Lemma 2.1, there exists a point in such that and. If belongs to , then by Lemma 2.5. The claim follows since implies and Lemma 2.4 implies. If does not belong to , then by Lemma 2.6. Thus. The claim now follows by Lemma 2.4, since the ratio of to is at most 3.

n V a uj8m 0 a 8

Proof: Assume without loss of generality that belongs to and is empty.

a n a

Lemma 2.7 For any point

Lemma 2.6 Let.

Lemma 2.5 Let

Proof: If

Lemma 2.4 Let

which is equal to

Proof: Note that
Lemma 2.3 For any conguration

Lemma 2.2 Let

Proof: If there is no such point

Lemma 2.1 For any point

For any point

and any conguration

charge

be distinct points in

, there exists a point
4. The claim now. If such a point , respectively. then

5 a

3 Online Median Placement
In the previous section, we found that a simple greedy algorithm yields interesting results for the facility location problem. Ideally, we would like to formulate a similar algorithm for the online median problem. The most obvious greedy algorithm is to select as the next point in the ordering the one that minimizes the objective function. Unfortunately, this algorithm gives an unbounded competitive (resp., approximation) ratio for the online median (resp., -median) problem. To see this, consider an instance consisting of points, one red and the rest blue, such that the following conditions are satised: the red point has weight ; each blue point has weight ; the distance from the red point to any blue point is ; the distance between any pair of distinct blue points is. The aforementioned greedy algorithm chooses the red point rst in the ordering, since that gives a cost of while choosing any other point gives a cost of. But then the ratio for a conguration of size is unbounded since the greedy cost is and the optimal cost is. (This example also shows that no online median algorithm can achieve a competitive ratio below.) We show that a more careful choice of the point, which we call hierarchically greedy, works well. Let (resp., ) denote the largest (resp., smallest) distance between two distinct points in the metric space. We dene a certain ball about each point, and select a ball of maximum value. But rather than simply choosing the center of ball as the next point in the ordering, we apply the approach recursively to select a point within. At each successive level of recursion, we consider geometrically smaller balls about the levels of recursion, we arrive at a ball containing only a single remaining candidate points. Within point, and we return this point as the next one in the ordering. Note that whereas the greedy algorithm discussed in the previous paragraph makes a single greedy choice to select a point, the hierarchically greedy greedy choices per point. algorithm makes Throughout this section, let , , , and denote real numbers satisfying the following inequalities.

The online median algorithm of Section 3.1 below makes use of the following additional denitions. A child of a ball is any ball where. For any point , let denote the ball. For any point and conguration , let denote the ball. For any nonempty sequence , we let (resp., ) denote the rst (resp., last) element of.

3.1 Algorithm

While the ball Let
has more than one child, append a maximum value child of.

5 a 8 a c

denote the singleton sequence.
is a maximum value ball in

e8 a 0 3dXQX} i 5

} f tt8 a ct5Td6Q a H@ gda 8 a c 5
, execute the following steps:
t 8 s 5 ut0 g3dXQ s 0 dt
G f Dm V m De G 8G 5 fD D m G

8xgx 5

G B G G

8 5 l t

8 o8 s Rt8t v 87 6RTx8 x30 5

a a y

C@ I

f 1 n y y

(1) (2) (3) (4)
The output of the online median algorithm is a collection of point sets such that , , and ,. Note that it is sufcient for an implementation of the algorithm to maintain the ball , as opposed to the entire sequence. The sequence has been introduced in order to facilitate the analysis. We discuss two implementations of the online median algorithm in Section 3.4. The rst implementation has a slightly superlinear running time. The second implementation runs in linear time, but assumes a (linear) preprocessing phase in which all distances are rounded down to the nearest integral power of. (Note that for the preprocessing phase to be well-dened, we require.) If the input distance function is a metric, it is straightforward to see that such rounding produces a -approximate metric.

3.2 Competitive Ratio

Before proceeding with the analysis, we introduce a number of additional denitions.
For any conguration , we partition into point in , we choose a point in such that For any conguration and For any conguration as.
In this section we present our main result, Theorem 2 below. In order to minimize the competitive ratio of implied by the theorem, we set to , set to approximately and set and to the right-hand sides of Equations (3) and (4), respectively. We thereby establish a competitive ratio of slightly below for the online median problem. In Section 3.4 we describe a linear-time implementation of the online median algorithm for which the parameter is required to be strictly greater than. The degradation in the competitive ratio that results by setting greater than can be made arbitrarily small by choosing sufciently close to.
Proof: Let there is a point in
f0 E 8 s0 U8G m 5 D @ 5 U8G m 5 D @ U m5 { t675 cC930 6xgcC|D g|j1TCg|30 m { D 75 m{D @ 8 @ 5 T6 1A5 8 0 dtt 5 5 @ 5 8 0 dt

. Note that. Hence

. Also, by the denition of
. The claim follows since
Lemma 3.1 For any conguration.

, point

, and point

m 5 @ 3sQ`usQ

Proof: Let
and let and Lemmas 3.2, 3.4, and 3.5 below.

m 5 D 0 Vc8 t0 `T 0 s 5

d dl 8 dQ 83sQ` 5 m@ 5 @ B 8 st @ @ 8 sk U 8 G m 5 D n 5 sQ`ctA8 dQ s
Theorem 2 For any conguration
. Note that. Thus the theorem follows immediately from

P txqwu

s 8r3t0 QT 0 s 5 s

and set of points

For any conguration
denote the unique point in
5 3sQT 30t0 c 3sk 8 s s 5 8 s 5 3t0 kgut0 Q s s 8t0 c` 3st0 c 8t0 Q 7 s 7 @ 8 s5 Blt675 s us 8ut0 5c} is i s i 2U 8 s 5 @ 5 67utWhk830s f Af a geda

and add

as follows: For each to. as
, and set of points , we dene

, we dene. as

@ Af BXi a qi
8 c 5 f geda a la 5 3sk G x30 dtt 7 a

Xw 8G m 5 D Fctn

8 s0 U 8 t675 G

y y y y y

5 E 5 t8 X3Tx6HA8 6r 5 @ 5 a k l 8 a " tt8 X cXt 30 h m @ @ 5 a E 8 D o dAuc5 E Do 5 @ eE30 6CA8 a @ H fe 5 E f~6 a 75 @ Xa 0 3dtQ@Ca 8 a X3H@h 8 a BlT5 5 @a E 1A8 a @ 30 B a
belong to. Then and let. ; (ii) belong to. If and ; (iii) the successor of in
5 sQ`t 8 0 3dXQ6 j W s
s P|t 8 0 5dt59 m1t 8 0s5lcQ0sBrcD t 8 skcQ 0 d 8 5 {8G m s s

cost and point in ,.

Lemma 3.2 For any conguration
8 t 8 G m 5 D m 5 { D dhcl|T st0 5kQ 0 dQ`7 @1A@ 5 k 8 0 gdt P|t5dt9t8 t0 lQs`xcD t8 t 5 m s 5 {8 G m 0 s s s s P 38t8 0t0 TRsGBcD 4t8 t0 TR0 d5 s 5 U 8 m 0 s 5 s 0t0 T 7 P3t 8 0sTRs5UGBmc5D 4t 8 0stR 0 d5 s
, and point. Note that in , in for some in. It follows that in. , we obtain. Thus, for any
Proof: Assume that in , is at most times
P 38t 8 0 dtX6B8t 8 st0 AQs 5 m 0 @ k 9 k 6 k 6 rx T5U8T 85RU8tm5 48T5RU m 5 GCxcD 5 8 0 gdtt 5 kcQr0 d5

Lemma 3.6 Let

In this section we establish our main technical lemma, Lemma 3.5.
Proof: Let be a point in such that. If then and denote the predecessor of in and assume inductively the result is immediate. Otherwise, let that. Note that and. Thus , where the last step follows from Equation (4).
Lemma 3.7 Let belong to the following claims hold: (i) it , satises

3.3 Proof of Lemma 3.5

Proof: The claim follows by summing the inequality of Lemma 3.3 over all
Lemma 3.4 For any conguration
Lemma 3.3 For any conguration
The claim now follows by summing the above inequality over all
Proof: Summing the inequality of Lemma 3.1 over all
Lemma 3.5 For any conguration
Our main technical lemma is stated below. The proof is given in the next subsection.

7. , then , call

Combining the two inequalities and applying Equation (4), we obtain
Multiplying through by and rearranging, we get , establishing the claim. by part (i) and Equation (3). Thus has at least two For part (ii), note that children; the claim follows. For part (iii), we use Equations (2) and (3) and part (i) to observe that

For ease of notation, throughout the remainder of this section we x a conguration , and let denote. We now describe a pruning procedure that takes as input the sequences , , and produces. The sequence is initialized to ,. The (nondeterministic) as output sequences , pruning procedure then performs a number of iterations. In a general iteration, the pruning procedure checks whether there exist two balls and in distinct sequences and , respectively, such that and. If not, the pruning procedure terminates. If so, the sequence is redened as the proper sufx of (the current) beginning at the successor of. Note that part (ii) of Lemma 3.7 ensures that the pruning procedure is well-dened. Furthermore, the procedure is guaranteed to terminate since each iteration reduces the length of some sequence.
Proof: Immediate from the denition of the pruning procedure. Lemma 3.9 Each sequence

is nonempty.

Proof: Immediate from part (ii) of Lemma 3.7 and the denition of the pruning procedure.

Lemma 3.8 Let

belong to

and let

m f930 6

P aP f a f a s

@ t0 7%

aP m 2e@ BAf a P

@ 30 B

5 t8 gx36rt

which is at most
by Equation (3). It follows that
is contained in a child of. Thus

E 5 A8 x6

@ f 74 E 1B99U d 85 d6 PD A0&m 8 'mxU G 5
8 gx 0 G G j6D % Cm f ! m G U D D G m IU D D GH EF 'UQQUme ~1`De'eBD m U m C m m A h630 6@D 70 m 5

G 3D m m

mx7 D o8G ur5
P D 0 m m 5 G g&2U f ! m m m % mUUU ! 01)UQQUm % U mx(he'&$QQm m #" D 5 D a 5 m m 7 8 a E
. For part (i), we know that

8 a 75 X@ 5

by Lemma 3.6. Also, we have

Proof: Since

Lemma 3.11 Let
Proof: If belongs to , then is nothing to prove. Otherwise, median algorithm, and the claim follows by Lemma 3.10. Lemma 3.12 Let
Proof: We prove that the claim holds before and after each iteration of the pruning procedure. Initially, and the claim holds by Lemma 3.11. If the claim holds before an iteration of the pruning procedure, then it holds after the iteration by part (iii) of Lemma 3.7.

Lemma 3.13 For any uncovered ball Proof: Note that
Let denote the set of all indices in such that some ball in is covered. We now construct a matching between the sets and as follows. First, for each in , we match with a point in that belongs to the last covered ball in the sequence. (Note that such a point is guaranteed to exist by the denition of. Furthermore, Lemma 3.8 ensures that we do not match the same point with more than one index.) Second, for each in in turn, we match with an arbitrary unmatched point in. We now construct a function mapping each point in to an uncovered ball. For each in that is matched with an index in , we set to. For each in that is matched with an index in , we set to the successor of the last covered ball in unless is covered, in which case we set to the ball. Lemma 3.14 For any pair of distinct points and in ,.
Proof: Immediate from Lemma 3.8 and the fact that the ball Lemma 3.15 For any point in ,
Proof: If is matched with an index in , the claim follows by Lemma 3.12. If is matched with an index in , we consider two cases. If is covered, then since has exactly one child. The claim follows since. If is uncovered, then the predecessor of in , call it , exists and contains. It follows that , where is the child of centered at. Let denote the ball.
8 Q 5 xR0 3dt 8 X@ 8r6 hE~t8 ~56r 5 @ x30 7C 8 a P xR0 3dt8 ~ @ 8 Q 5 @ a P5c a %@ a PWx { T | 88 Q 5 5 E 5 tS0 dt9hts
8 a Pc @Ck67~ 8 s 8 ~ 8 ~T 8 a P a P 8 PgX s 5 T | Vx { ~ s s a s T | Ux { T aP s T s x { | | x { T aP W E 2U 8 s 5 W E 5 856r@l8672t7565 67Rut~3s` 5 U5 6hE~83sQ` 30 C @ 8 s ft@ 30 B

A ball

8 t3dt6r t8 X3Tx 5 E 5 t8 a 0 53dtQa5 6rt it8 a 0 dta tX @ 8 @ 5 a P8 Q 5 5 E 5 3t8XR0 3dtQ6rtht8 a X3Tx6 BAf 5 5 0 dttx a 5 5 3dtQ6rt
, be a point and assume that. Then , so is dened to be covered iff
P3t8xS0 53dXQ56ht8 a PXQ E 5 BAf
be a point and assume that
8t3dtcXtht8 a 5 5 E 8 P 38t3dXQ6ht8 a 5 E 8 fxhAf

. Then ,. 9

Lemma 3.10 Let

8 o AX@ 5 a P 8 ~

. Then

. The claim follows.

and there by the denition of the online

a B@ a P

. A ball is uncovered iff it is not covered.

is contained in

Lemmas 3.13, 3.14, and 3.15 together yield a proof of Lemma 3.5.

3.4 Time Complexity

In this section we describe two implementations of the online median algorithm given in Section 3.1. Throughout this section, let denote the quantity. The rst implementation runs in time. The second implementation runs in time and assumes an -time preprocessing phase in which all distances are rounded down to the nearest integral power of. To analyze the running time of the implementations given below, we make use of the following lemma.

Proof: First, note that. By Lemma 3.6,. Combining these inequalities and using Equation (4), we obtain
In the rst implementation, for each point in , we sort the remaining points by their distance from. The total sorting time is. Using these sorted arrays, we can compute the value of any given time. We also maintain the distance from to the nearest point in. Note that ball in can be determined in constant time given and. The total time to maintain such distances is thus. It follows that the rst step of each iteration can be implemented in time. The total time for the second step is times the sum over all balls appearing in some sequence , , of the number of children of. By Lemma 3.16, it is straightforward to see that the latter sum is , and thus the total time for the second step is. The running time of the third step is negligible. Thus the running time of the rst implementation is , as claimed above. For the second implementation, note that after the preprocessing phase, there are distinct distances. Thus, for each point , time is sufcient to construct an -sized table that can be used to compute the value of any ball in time. It follows that the total time for the second step can be improved to. The running time of the second implementation is therefore , which is linear in the size of the input (in bits). 10

8 geda f 5

5 6Hk1

Qcz Af a

8 z m 5 Q
8 G m P dBF5 G f G RU hm U 8 G U f5

8~tUzmt 8 5 tQcz

Lemma 3.16 Let in sequence. If
be a child of a ball then.

in sequence

be a child of a ball

8 U8z m 55 tej~t

c830 "@
8 G5tH8UQQUmt5h8 a o U o m 5 8G 5 jdmh A @ x30 "

8 z 5 QFm x t

8t5 G 8 8z m 5 j

which is less than of.

by Equation (4). The desired inequality follows since
Below we complete the proof of the claim by showing that , which implies that. It remains to prove that in the nal case considered above. We have

by the denition

and hence

E A8 a

0 G m j6D % f G ! U ! h6D m D m % UQQUm |8 a 5 D 48 a 0 m {

E o fX

8 6hA6rt 5 E t Qcz

8 a  5

4 Concluding Remarks
We plan to investigate whether the ideas presented above can be applied to other problems. The work of Indyk [8] gives a technique to achieve sublinear time bounds for various location problems through random sampling of the distance function; we would like to see if application of these techniques to our algorithms yield sublinear time bounds. Korupolu et al. [12] give an algorithm and an efcient distributed implementation for hierarchical cooperative caching in which the distance function is an ultrametric. We would like to see if the hierarchical greedy strategy can be used or extended to solve the problem for an arbitrary metric space. It would also be interesting to see if the hierarchical greedy strategy admits an efcient distributed implementation for this problem. A nice feature of our online median algorithm is its simplicity. Although we deal with a harder problem, the algorithm is actually simpler to specify than existing constant-factor approximation algorithms for the -median problem. It would be interesting to see whether our approach could be simplied to yield a fast -median algorithm achieving a small approximation ratio.

References

[1] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, UK, 1998. [2] M. Charikar and S. Guha. Improved combinatorial algorithms for facility location and -median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, October 1999. To appear. [3] M. Charikar, S. Guha, E. Tardos, and D. B. Shmoys. A constant-factor approximation algorithm for the -median problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 110, May 1999. [4] F. A. Chudak. Improved approximation algorithms for uncapacitated facility location. In R. E. Bixby, E. A. Boyd, and R. Z. Ros-Mercado, editors, Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pages 180194, Berlin, 1998. Springer. [5] W. Domschke and A. Drexl. Location and Layout Planning: An International Bibliography, volume 238 of Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, Berlin, 1985. [6] M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, MA, 1995. [7] S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 649657, January 1998. [8] P. Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 428434, May 1999. [9] S. Irani and Karlin A. R. Online computation. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston, MA, 1995. [10] K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and median problems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, October 1999. To appear. 11
[11] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a local search heuristic for facility location problems. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 110, January 1998. [12] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Placement algorithms for hierarchical cooperative caching. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 586595, January 1999. [13] A. A. Kuehn and M. J. Hamburger. A heuristic program for locating warehouses. Management Science, 9:643666, 1963. [14] J.-H. Lin and J. S. Vitter. Approximation algorithms for geometric median problems. Information Processing Letters, 44:245249, 1992. [15] J.-H. Lin and J. S. Vitter. -approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 771782, May 1992. [16] P. Mirchandani and R. Francis, editors. Discrete Location Theory. Wiley, New York, NY, 1990. [17] D. B. Shmoys, E. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 265274, May 1997.