Techniques for performing association and resource partitioning in a wireless network with relays are described. In an aspect, resource partitioning may be performed to allocate available resources to nodes and access/backhaul links of relays. In one design, a node computes local metrics for a plurality of possible actions related to resource partitioning. The node receives local metrics for the possible actions from at least one neighbor node and determines overall metrics for the possible actions based on the computed and received local metrics. The node determines resources allocated to a set of nodes and resources allocated to the access and backhaul links of at least one relay based on the overall metrics for the possible actions. In another aspect, association involving relays may be performed by taking into account the performance of the relays. In yet another aspect, association and resource partitioning may be performed jointly.