Timely identification of floods is crucial for preserving lives and assessing damage. To ensure effective flood protection, it is imperative to have consistent real-time mapping of flooded regions. Floods often occur in specific weather conditions, accompanied by cloud cover due to excessive precipitation. Remote sensing, primarily using multi-spectral imagery from optical sensors and backscatter data from synthetic aperture radar (SAR), plays a vital role in delineating flood extents. SAR remote sensing, known for its all-weather capabilities, is widely adopted for flood mapping, providing continuous day and night coverage. This study utilized Sentinel-1 satellite datasets to map floods across 11 events, employing the DB-SEN1FloodNet model, achieving outstanding performance metrics.

Global cities are increasingly experiencing severe heat-related issues due to rising global temperatures and urban heating. Vulnerable groups are particularly at risk of experiencing heat-related diseases. To effectively plan mitigation strategies, it is essential to have information on the areas with the highest urban heating and the presence of vulnerable populations. The current study aims to determine the persistent UHI and quantify its impact on the children and elderly population in the NCR, India. The study used MODIS LST data from 2000 to 2021 and the age structure population data for the analysis. The study's findings showed that more than 75% of the susceptible groups reside in the 10% of the study region that is part of a high-impact zone, which is particularly dangerous due to heat-related hazards. These findings emphasize the critical need for targeted strategies and actions to reduce the negative effects of urban heating on disadvantaged communities.

Urban Green Spaces (UGS) constitute a crucial component of the urban landscape, contributing significantly to the quality of urban life. Therefore, it is imperative for urban planners to use effective tools and formulate suitable metrics for regular mapping and monitoring of the urban greening and deforestation trends in neighborhoods, regardless of their size. To this end, this study uses a geospatial approach to evaluate the distribution of UGS, considering factors related to quantity and quality. The study focuses on Bhopal city of India. The indicators for UGS distribution were derived from remote sensing data, allowing for cost-effective assessments at desired time intervals. According to the findings, Bhopal’s UGS significantly declined, became fragmented, and disintegrated between 2010 and 2020. The different neighborhoods went through varying degrees of degradation. The methodology adopted facilitates an intra-city analysis of green cover patterns, emphasizing the need to allocate space for greenery in urban planning for comprehensive well-being.

Semantic segmentation is crucial for accurately understanding and monitoring Land-Use-Land-Cover (LULC) changes. To address challenges like ground object complexity and edge loss, we propose the MC-SegNext model. This model integrates a Convolutional Block Attention Module (CBAM), a multi-head self-attention mechanism, and a proposed Sequential-Atrous Spatial Pyramid Pooling (S-ASPP) module into the existing DeepLabv3+ encoder-decoder framework. Unlike the parallel atrous convolutions in the original DeepLabv3+, the S-ASPP module sequentially combines their outputs to preserve individual contributions. The proposed S-ASPP strategy sequentially combines the influence of each atrous convolution to better retain the contribution of each atrous convolution. By combining S-ASPP technique and attention mechanisms, the model can effectively gather spatial information and enhance multi-scale features. Our model was tested on open datasets, including ISPRS Potsdam, ISPRS Vaihingen, and LoveDA Urban and Rural. It was compared with state-of-the-art models using metrics such as IoU, F1-score, and accuracy. Results showed that MCSegNext improved mean Intersection over Union (mIoU) by 4.51% on the ISPRS Potsdam dataset, 4.08% on the Vaihingen dataset, 4.41% on LoveDA Urban, and 4.68% on LoveDA Rural compared to DeepLabv3+.

Groundwater is vital for sustaining ecosystems, agriculture, and human communities by serving as a reliable source of drinking water and irrigation. It plays a crucial role in maintaining river flows and wetlands, supporting biodiversity, and mitigating the effects of droughts. Continuing monitoring groundwater resources is essential for long-term sustainability and water resource management. This study works on assimilating time-series SAR Interferometry and GRACE datasets for monitoring groundwater dynamics in the southern Punjab region of India.

Light Detection And Ranging (LiDAR) remote sensing technology efficiently produces accurate 3D geometry of the forest structure in the form of point cloud data. Individual tree parameters can be measured more effectively using LiDAR technology. LiDAR can penetrate through the dense canopies and produce adequate information of each tree for forest inventory and mensuration. The main objective of this case study is to bring out the potential of integrating (Terrestrial Laser Scanner) TLS and (Airborne Laser Scanner) ALS to compensate for each other limitations and to generate a complete and accurate 3D model of the forest structures. Tree height and DBH were measured from TLS, ALS, and Integrated point cloud data. It is observed that TLS and ALS integrated point cloud data have shown more promising results when compared to individual LiDAR technologies. Both technologies are complementary to each other. We found that integration of ground perspective LiDAR and above canopy LiDAR has excellent potential in producing plot-level completeness of information which can be used for AGB calculations and other forest parameters extraction. The ALS and TLS datasets used in this case study are a part of the SilviLaser 2021 Benchmark Dataset acquired in the Lower Austria region.

The recent advancements in close-range remote sensing techniques are creating opportunities to explore more about the forest ecosystem more precisely. The Light Detection and Ranging (LiDAR) scanners are a boon to forest applications because they provide detailed and precise information about the forest structure from ground to canopy top level. The point cloud data collected with Terrestrial Laser Scanner (TLS) must be processed to get exact information about the trees, including topographic terrain information in the forests. Tree parameters are essential to calculate the total productivity of the forests and their monitoring. In this research, two forest plots were considered in the Zvolen district within central Slovakia; one forest plot (TLS_Plot1) consists of 49 trees, and the other (TLS_Plot2) consists of 102 trees. A total of nine TLS scans were performed in each of the forest plots. It is also crucial to segregate the unstructured 3D point cloud data into various classes for accurate information extraction of each feature in the forest, such as stem, canopy, terrain, dead wood, etc. Forest Structural Complexity Tool (FSCT) algorithm is one such algorithm that has been recently developed for point cloud classification. So, we are focusing on the classification function of this tool. The classification function is classifying the forest point cloud data into stems, leaves, some branches, wood debris, lying dead wood, etc. We tried to investigate the accuracy of stem classification obtained for the forest point cloud using the FSCT algorithm. But a qualitative assessment must be done to evaluate the accuracy of the point cloud classification obtained. For this reason, stems from both the forest point cloud were manually extracted and compared with the stems point extracted from the FSCT algorithm classification, and the accuracy was evaluated. The FSCT algorithm-based stem classification achieved accuracy for TLS_Plot1 and TLS_Plot2 is 94.80% and 96.28%.

In this study, we utilized Landsat time-series data from 2000 to 2020 to examine urban sprawl and Urban Density (UD) at five-year time-steps. To perform supervised classification and extract urban areas, we employed the Random Forest (RF) machine learning algorithm. We compared the expansion of urban density with the corresponding growth in Population Density (PD). PD was categorized into six classes - very low, low, moderate, high, very high, and crowded - based on a standard classification criterion. The percentage area lying in each class of PD was calculated for each year, allowing us to correlate the percentage growth in urban areas with population growth in different regions of the city. The findings clearly indicate a direct relationship between population increase and expansion of built-up areas. Notably, the largest population growth and urban land extension occurred in proximity to the city's major transportation networks, highways, marketplaces, and educational institutions.

Urban sprawl is becoming a serious challenge to growth, particularly in the developing nations. As a city's population and activities expand, the city boundary extends to accommodate growth at its urban fringes, resulting in fragmented urban morphology. In the current study, Landsat time-series data is used to analyse the urban growth and its pattern from 1995 to 2022 for Bhopal, the capital city of the Madhya Pradesh state of India. The spatiotemporal dynamics of urbanisation is analysed along with the various spatial metrics. Visualizing past trends and growth patterns allows planning authorities to effectively plan for essential infrastructure facilities such as water, electricity, and sanitation, catering to the needs of the growing population.

Augmented Reality (AR) is a technology that has attracted a lot of attention in recent times, especially, after PokemonGo and quite recently with the gaining popularity of metaverse. AR is not a new technology but its development to maturity has always been dependent on many other technologies like computer vision, mobile processing, optics, etc. We are at that stage in the development cycle of AR where all other technologies not only support but can benefit from its use. This research presents one such innovation in the domain of education - for school children or enthusiasts about geospatial technologies such as remote sensing. In this paper, we have discussed the idea, methodology, and demonstration of one such application which establishes a future trend for use of AR in the education of Geospatial Technology. Different types of remote sensing data, their acquisition method, satellite technology, and applications area are explained using AR for a more interactive experience. Learning about geospatial technology will be helpful as the new frontier of Geoinformation is enhancing everyone's day-to-day life and will help in boosting interest in this field.

Urbanization is a major dynamism that changes the landscape pattern of the city. Analyzing the landscape change pattern is important to understand the heterogeneity of the city and its interaction with the environment. The National Capital Region (NCR) is coverd with varying landscape pattern with the amalgamation of several urban agglomerations. The present study is attempted to compare the landscape pattern of highly urbanized areas of prominent cities in the NCR, i.e., Delhi, Gurgaon, and Noida. Normalized Differential Built Index (NDBI) is used for urban extraction and the overall accuracy of Delhi, Gurgaon and Noida is 75.25%,69.23%, and 77.73%. Based on the aspect of the urban landscape pattern, the analysis is carried out on a hierarchical scale at the Class and Landscape-level. The landscape pattern of the city is characterized by the Largest Patch Index (LPI), the Aggregation Index (AI), and the Percentage of Land (PLAND). Delhi is a highly dense urban landscape, with a high aggregation of urban class compared with Gurgaon and Noida

Reliable rail infrastructure helps in ensuring a state's economic stability. Timely detection of missing rail fasteners is crucial in avoiding fatal accidents and plays a significant role in rail safety assurance. In this paper we propose the use of one-stage RetinaNet deep convolution network architecture to detect rail fasteners on rail tracks by analyzing the aerial imagery. Quantitative assessment was conducted in a one km railway stretch by acquiring aerial images of size 5472×3078, using a DJI Phantom 4 from a height of 100m. However, the background complexity renders it as a demanding task. Results demonstrate that the learned deep features promise a robust method, if trained on a larger dataset and can help identify rail anomalies which may require imminent repair.

The study presents a comparative analysis of the three urban growth prediction models, i.e., SLEUTH, Markov Chain-Cellular Automata (MC-CA), MC-Multi-layer perceptron (MLP). The capability of these models is assessed for predicting urban growth of Lucknow city, India, for the year 2025. The study resulted in various merits and demerits of the models. The calibration and validation are carried out on remote sensing satellite data of 1995, 2005, 2009 and 2016. The resulted kappa coefficients for CA-MC, MC-MLP and SLEUTH are 0.66, 0.74 and 0.76, respectively. SLEUTH and MC-CA resulted in optimum accuracy, whereas, MC-CA performed most accurately in terms of influential based growth of the city.

Microwave Remote Sensing using SAR interferometry is a major tool for the land deformation monitoring. The time series InSAR techniques like PsInSAR are quite efficient for retrieving the land deformation using permanent scatterer candidates information. The study area is selected as the city of Lucknow, capital of Uttar Pradesh state in India. This study utilizes Sentinel-1 IW mode TOPS 58 ascending and 59 descending modes datasets. The land subsidence was retrieved using both the ascending and descending pass datasets separately followed by the integration of ascending and descending mode displacement velocity vectors.

We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a 1−ϵ fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor ϵ approaches 0 when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast ϵ approaches 0, is near optimal: We give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a 1−ϵ fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. Further, if the algorithm is given one number per distribution, namely the optimal profit possible for each of the adversary’s distribution, then we design an algorithm that achieves a 1−ϵ fraction of the weighted average of the optimal profit of each distribution the adversary picks. In the offline setting we give a fast algorithm to solve very large linear programs (LPs) with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1+ϵ) the mixed packing-covering problem with O (γ m log ( n /δ)/ϵ 2 ) oracle calls where the constraint matrix of this LP has dimension n × m , the success probability of the algorithm is 1−δ, and γ quantifies how significant a single request is when compared to the sum total of all requests. We discuss implications of our results to several special cases including online combinatorial auctions, network routing, and the adwords problem.

No abstract available.

Surface temperature is one of the most important parameter for estimating the effect of climatic change on glaciers and it is a key requirement for input to energy balance models. For the Indian Himalayas, such measurements are scarce and difficult to obtain. Weather station network is very sparse and mostly weather stations are established near around glacier terminus or far from glaciers at lower. Since temperature analysis of different altitude zones are important for observing the effects of climate change with respect of altitude. Unfortunately, estimating surface temperature using traditional weather-station based meteorological observations is not a feasible solution for upper reach of glaciers. Therefore, through remote sensing studies, a synoptic view of the Himalayan region can be established, and used for regional climatological studies. In this paper, an attempt has been made to analyze the relationships between glacier surface temperature with altitude and location.

Terrestrial Water Storage (TWS) in the Bhagirathi Ganga and Vishnu Ganga basins is an important hydrologic component for the Ganga River. Improved estimation of TWS in the Bhagirathi Ganga and Vishnu Ganga basins is crucial for water resources management for India. Despite its importance, storage and change of TWS in the study area has not been well studied at a larger scale. In this investigation, TWS and its change (TWSC) is estimated in the Bhagirathi Ganga and Vishnu Ganga basins during the period of 2004 to 2010. TWS is calculated from two methods: The first method employs the GRACE remote sensing satellite while the second employs estimation by use of climate data of study area provided by NOAA. TWSC is estimated from the TWS by subtraction of two consecutive monthly values. In addition, Total water storage change is also estimated from a water balance approach using a combination of precipitation, runoff and transevaporation. The spatial average values of GRACE and NOAA from 1°×1° spatial resolutions was extracted using a watershed mask derived from the DEM of the Bhagirathi Ganga and Vishnu Ganga basins. The TWS result from the GRACE and NOAA show decreasing trend in TWS of 0.54 cm/year and 0.2 cm/year, respectively due to decrease in precipitation, high evaporation of the study area. The results indicate the great potential of GRACE and water balance approach using NOAA data for providing hydrological information to water resource management in Uttarakhand.

The first-price auction is popular in practice for its simplicity and transparency. Moreover, its potential virtues grow in complex settings where incentive compatible auctions may generate little or no revenue. Unfortunately, the first-price auction is poorly understood in theory because equilibrium is not a priori a credible predictor of bidder behavior.

We give a simple proof that the ranking algorithm of Karp, Vazirani and Vazirani [KVV90] is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by Agarwal et al. [AGKM11]. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgeted allocation problem with small bids (also called the AdWords problem) of Mehta et al. [MSVV05].

Despite the pervasiveness of markets in our lives, little is known about the role of user interfaces (UIs) in promoting good decisions in market domains. How does the way we display market information to end users, and the set of choices we offer, influence users' decisions? In this paper, we introduce a new research agenda on "market user interface design." Our goal is to find the optimal market UI, taking into account that users incur cognitive costs and are boundedly rational. Via lab experiments we systematically explore the market UI design space, and we study the automatic optimization of market UIs given a behavioral (quantal response) model of user behavior. Surprisingly, we find that the behaviorally-optimized UI performs worse than the standard UI, suggesting that the quantal response model did not predict user behavior well. Subsequently, we identify important behavioral factors that are missing from the user model, including loss aversion and position effects, which motivates follow-up studies. Furthermore, we find significant differences between individual users in terms of rationality. This suggests future research on personalized UI designs, with interfaces that are tailored towards each individual user's needs, capabilities, and preferences.

We consider a significant generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable. The problem considers a sequence of items arriving online that have to be allocated to agents, with different agents bidding different amounts. The objective function is the sum, over each agent i, of a monotonically non-decreasing concave function Mi : R+ -> R+ of the total amount allocated to i. All variants of online matching problems (including the Adwords problem) studied in the literature consider the special case of budgeted linear functions, that is, functions of the form Mi(ui) = min {ui,Bi} for some constant Bi. The distinguishing feature of this paper is in allowing arbitrary concave returns. The main result of this paper is that for each concave function M, there exists a constant F(M) ≤ 1 such that: there exists an algorithm with competitive ratio of miniF(Mi), independent of the sequence of items. No algorithm has a competitive ratio larger than F(M) over all instances with Mi= M for all i.

We present algorithms for a class of resource allocation problems both in the online setting with stochastic input and in the offline setting. This class of problems contains many interesting special cases such as the Adwords problem. In the online setting we introduce a new distributional model called the adversarial stochastic input model, which is a generalization of the i.i.d model with unknown distributions, where the distributions can change over time. In this model we give a 1-O(ε) approximation algorithm for the resource allocation problem, with almost the weakest possible assumption: the ratio of the maximum amount of resource consumed by any single request to the total capacity of the resource, and the ratio of the profit contributed by any single request to the optimal profit is at most (ε2/log(1/ε)2)/(log n + log (1/ε)) where n is the number of resources available. There are instances where this ratio is #949;2/log n such that no randomized algorithm can have a competitive ratio of 1-o(ε) even in the i.i.d model. The upper bound on ratio that we require improves on the previous upper-bound for the i.i.d case by a factor of n.

The next decade will see an abundance of new intelligent systems, many of which will be market-based. Soon, users will interact with many new markets, perhaps without even knowing it: when driving their car, when listening to a song, when backing up their files, or when surfing the web. We argue that these new systems can only be successful if a new approach is chosen towards designing them. In this paper we introduce the general problem of "Hidden Market Design." The design of a "weakly hidden" market involves reducing some of the market complexities and providing a user interface (UI) that makes the interaction seamless for the user. A "strongly hidden market" is one where some semantic aspect of a market is hidden altogether (e.g., budgets, prices, combinatorial constraints). We show that the intersection of UI design and market design is of particular importance for this research agenda. To illustrate hidden market design, we give a series of potential applications. We hope that the problem of hidden market design will inspire other researchers and lead to new research in this direction, paving the way for more successful market-based systems in the future.

The Internet has allowed market-based systems to become increasingly pervasive. In this paper we explore the role of user interface (UI) design for these markets. Different UIs induce different mental models which in turn determine how users understand and interact with a market. Thus, the intersection of UI design and economics is a novel and important research area. We make three contributions at this intersection. First, we present a novel design paradigm which we call hidden markets. The primary goal of hidden markets is to hide as much of the market complexities as possible. Second, we explore this new design paradigm using one particular example: a P2P backup application. We explain the market underlying this system and provide a detailed description of the new UI we developed. Third, we present results from a formative usability study. Our findings indicate that a number of users could benefit from a market-based P2P backup system. Most users intuitively understood the give & take principle as well as the bundle constraints of the market. However, the pricing aspect was difficult to discover/understand for many users and thus needs further investigation. Overall, the results are encouraging and show promise for the hidden market paradigm.

Cellular radios consume more power and suffer reduced data rate when the signal is weak. According to our measurements, the communication energy per bit can be as much as 6x higher when the signal is weak than when it is strong. To realize energy savings, applications must preferentially communicate when the signal is strong, either by deferring non-urgent communication or by advancing anticipated communication to coincide with periods of strong signal. Allowing applications to perform such scheduling requires predicting signal strength, so that opportunities for energy-efficient communication can be anticipated. Furthermore, such prediction must be performed at little energy cost.

Cellular radio communication is a significant contributor to battery energy drain on smartphones, in some cases inflating the energy cost by a factor of 5 or more compared to the energy cost of the base device. Stratus is a system to reduce this energy consumption by leveraging cloud resources to make data communication on smartphones more efficient. Using a cloud-based proxy, Stratus employs optimizations that adapt an application's incoming and outgoing traffic to better match the energy characteristics of the radio interface. The optimizations include (a) aggregation to bunch up sporadic transmissions, (b) asymmetric dictionary-based compression to reduce the number of bits transmitted over the air, and (c) opportunistic scheduling to avoid communication during periods of poor signal reception. These optimizations can be used individually, or in combination, subject to an application's delay tolerance. For example, using our Stratus prototype, the aggregation and compression optimizations together achieve up to 50% energy savings for web browsing, while the aggregation and scheduling optimizations together achieve up to 35% energy savings for a media streaming application.

We derive efficient algorithms for both detecting and representing matchings in lopsided bipartite graphs; such graphs have so many nodes on one side that it is infeasible to represent them in memory or to identify matchings using standard approaches. Detecting and representing matchings in lopsided bipartite graphs is important for allocating and delivering guaranteed-placement display ads, where the corresponding bipartite graph of interest has nodes representing advertisers on one side and nodes representing web-page impressions on the other; real-world instances of such graphs can have billions of impression nodes. We provide theoretical guarantees for our algorithms, and in a real-world advertising application, we demonstrate the feasibility of our detection algorithms.

We study bargaining networks, discussed in a recent paper of Kleinberg and Tardos [KT08], from the perspective of cooperative game theory. In particular we examine three solution concepts, the nucleolus, the core center and the core median. All solution concepts define unique solutions, so they provide testable predictions. We define a new monotonicity property that is a natural axiom of any bargaining game solution, and we prove that all three of them satisfy this monotonicity property. This is actually in contrast to the conventional wisdom for general cooperative games that monotonicity and the core condition (which is a basic property that all three of them satisfy) are incompatible with each other. Our proofs are based on a primal-dual argument (for the nucleolus) and on the FKG inequality (for the core center and the core median). We further observe some qualitative differences between the solution concepts. In particular, there are cases where a strict version of our monotonicity property is a natural axiom, but only the core center and the core median satisfy it. On the other hand, the nucleolus is easy to compute, whereas computing the core center or the core median is #P-hard (yet it can be approximated in polynomial time).

Perhaps the strongest notion of truth-revealing in a cost sharing mechanism is group strategyproofness. However, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. We present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to its application. Our class includes the Dutta–Ray egalitarian method as a special case. It also includes a new cost sharing method, which we call the opportunity egalitarian method.

We define a new class of markets, the Eisenberg-Gale markets. This class contains Fisher's linear market, markets from the resource allocation framework of Kelly kelly, as well as numerous interesting new markets.We obtain combinatorial, strongly polynomial algorithms for severalmarkets in this class.

We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their utility by equalizing their return-on-investment across all keywords. We show that existing auction mechanisms combined with this heuristic can experience cycling (as has been observed in many current systems), and therefore propose a modified class of mechanisms with small random perturbations. This perturbation is reminiscent of the small time-dependent perturbations employed in the dynamical systems literature to convert many types of chaos into attracting motions. We show that the perturbed mechanism provably converges in the case of first-price auctions and experimentally converges in the case of second-price auctions. Moreover, the point of convergence has a natural economic interpretation as the unique market equilibrium in the case of first-price mechanisms. In the case of second-price auctions, we conjecture that it converges to the "supply-aware" market equilibrium. Thus, our results can be alternatively described as a tâtonnement process for convergence to market equilibriumin which prices are adjusted on the side of the buyers rather than the sellers. We also observe that perturbation in mechanism design is useful in a broader context: In general, it can allow bidders to "share" a particular item, leading to stable allocations and pricing for the bidders, and improved revenue for the auctioneer.

We provide the first polynomial time exact algorithm for computing an Arrow–Debreu market equilibrium for the case of linear utilities. Our algorithm is based on solving a convex program using the ellipsoid algorithm and simultaneous diophantine approximation. As a side result, we prove that the set of assignments at equilibrium is convex and the equilibrium prices themselves are log‐convex. Our convex program is explicit and intuitive, which allows maximizing a concave function over the set of equilibria. On the practical side, Ye developed an interior point algorithm [Lecture Notes in Comput. Sci. 3521, Springer, New York, 2005, pp. 3–5] to find an equilibrium based on our convex program. We also derive separate combinatorial characterizations of equilibrium for Arrow–Debreu and Fisher cases. Our convex program can be extended for many nonlinear utilities and production models. Our paper also makes a powerful theorem (Theorem 6.4.1 in [M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd ed., Springer‐Verlag, Berlin, Heidelberg, 1993]) even more powerful (in Theorems 12 and 13) in the area of geometric algorithms and combinatorial optimization. The main idea in this generalization is to allow ellipsoids to contain not the whole convex region but a part of it. This theorem is of independent interest.

Wireless LAN administrators often have to deal with the problem of sporadic client congestion in popular locations within the network. Existing approaches that relieve congestion by balancing the traffic load are encumbered by the modifications that are required to both access points and clients. We propose cell breathing, a well-known concept in cellular telephony, as a load balancing mechanism to handle client congestion in a wireless LAN. We develop power management algorithms for controlling the coverage of access points to handle dynamic changes in client workloads. We further incorporate hand-off costs and manufacturer specified power level constraints into our algorithms. Our approach does not require modification to clients or to the standard. It only changes the transmission power of beacon packets and does not change the transmission power of data packets to avoid the interactions with auto-rating. We analyze the worst-case bounds of the algorithms and show that they are either optimal or close to optimal. In addition, we evaluate our algorithms empirically using synthetic and real wireless LAN traces. Our results show that cell breathing significantly outperforms the commonly used fixed power scheme and performs at par with sophisticated load balancing schemes that require changes to both the client and access points

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, so far this conjecture could not be verified even for the simple network consisting of K3,2with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network.

We propose a novel platform for building off-line markets for digital content. The key objective is to enable an arbitrary user of specific digital content to resell it to other users in an off-line peer-to-peer manner so that part of the proceeds go to content's copyright holder. Most importantly, one part of the revenues is retained by the seller as an incentive for participating in the distributed economy. To address this objective, a transaction is finalized and incentives distributed to the seller on-line using a client-server architecture. Technologically, such systems can be readily created, for example, by adding a communication tool such as Bluetooth to a portable media player such as the iPod. We present a threat model for the proposed system and devise a novel protocol that relies on traditional public-key cryptography to ensure secure and efficient off-line transactions of arbitrary digital content. As a consequence, in our system copyright holders can control the pricing and recruit a powerful marketing and sales force with marginal investment and via various types of incentives, users are offered the ability to sell or purchase content they like anywhere, anytime, and to/from anyone.

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of K/sub 3,2/ with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network.

This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original sources. The work by Ho et al. 2004 demonstrates that random network coding can solve this problem at the potentially high cost of jointly decoding the source and the network code. Motivated by complexity considerations we consider the performance of separate source and network codes. Previous work by Effros et al. 2003 demonstrates the failure of separation between source and network codes for nonmulticast networks. We demonstrate that failure for multicast networks. We study networks with capacity constraints on edges. It is shown that the problem with two sources and two receivers is always separable. Counterexamples are presented for other cases.

Given a network of lossless links with rate constraints, a source node, and a set of destination nodes, the multicast capacity is the maximum rate at which the source can transfer common information to the destinations. The multicast capacity cannot exceed the capacity of any cut separating the source from a destination; the minimum of the cut capacities is called the cut bound. A fundamental theorem in graph theory by Edmonds established that if all nodes other than the source are destinations, the cut bound can be achieved by routing. In general, however, the cut bound cannot be achieved by routing. Ahlswede et al. established that the cut bound can be achieved by performing network coding, which generalizes routing by allowing information to be mixed. This paper presents a unifying theorem that includes Edmonds' theorem and Ahlswede et al.'s theorem as special cases. Specifically, it shows that the multicast capacity can still be achieved even if information mixing is only allowed on edges entering relay nodes. This unifying theorem is established via a graph theoretic hardwiring theorem, together with the network coding theorems for multicasting. The proof of the hardwiring theorem implies a new proof of Edmonds' theorem.

Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of K3,2with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network

We propose a scheme for building peer-to-peer overlay networks for broadcasting using network coding. The scheme addresses many practical issues such as scalability, robustness, constraints on bandwidth, and locality of decisions. We analyze the system theoretically and prove near optimal bounds on the parameters defining robustness and scalability. As a result we show that the effects of failures are contained locally, allowing the network to grow exponentially with server load. We also argue that adversarial failures are no more harmful than random failures.

In this paper, the network planning problem in wireless ad hoc networks is formulated as the problem of allocating physical and medium access layer resources or supplies to minimize a cost function, while fulfilling certain end-to-end communication demands, which are given as a collection of multicast sessions with desired transmission rates. We propose an iterative cross-layer optimization, which alternates between: 1) jointly optimizing the timesharing in the medium access layer and the sum of max of flows assignment in the network layer and 2) updating the operational states in the physical layer. We consider two objectives, minimizing aggregate congestion and minimizing power consumption, respectively, corresponding to operating in a bandwidth-limited regime and in an energy-limited regime. The end result is a set of achievable tradeoffs between throughput and energy efficiency, in a given wireless network with a given traffic pattern. We evaluate our approach quantitatively by simulations of community wireless networks and compare with designs that decouple the layers. We demonstrate that significant performance advantages can be achieved by adopting a full-fledged cross-layer optimization. Furthermore, we observe that optimized solutions generally profit from network coding, physical-layer broadcasting, and traffic-dependent physical states.

The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.

We prove the existence of tolls to induce multicommodity, heterogeneous network users that independently choose routes minimizing their own linear function of tolls versus latency to collectively form the traffic pattern of a minimum average latency flow. This generalizes both the previous known results of the existence of tolls for multicommodity, homogeneous users (Beckman et al., 1956) and for single commodity, heterogeneous users (Cole et al., 2003). Unlike previous proofs for single commodity users in general graphs, our proof is constructive - it does not rely on a fixed point theorem - and results in a simple polynomial-sized linear program to compute tolls when the number of different types of users is bounded by a polynomial. We show that our proof gives a complete characterization of flows that are enforceable by tolls. In particular, tolls exist to induce any traffic pattern that is the result of minimizing an arbitrary function from R/sup E(G)/ to the reals that is nondecreasing in each of its arguments. Thus, tolls exist to induce flows with minimum average weighted latency, minimum maximum latency, and other natural objectives. We give an exponential bound on tolls that is independent of the number of network users and the number of commodities. We use this to show that multicommodity tolls also exist when users are not from discrete classes, but instead define a general function that trades off latency versus toll preference. Finally, we show that our result extends to very general frameworks. In particular, we show that tolls exist to induce the Nash equilibrium of general nonatomic congestion games to be system optimal. In particular, tolls exist even when 1) latencies depend on user type; 2) latency functions are nonseparable functions of traffic on edges; 3) the latency of a set S is an arbitrary function of the latencies of the resources contained in S. Our exponential bound on size of tolls also holds in this case; and we give an example of a congestion game that shows this is tight; it requires tolls that are exponential in the size of the game.

We provide the first polynomial time exact algorithm for computing an Arrow-Debreu market equilibrium for the case of linear utilities. Our algorithm is based on solving a convex program using the ellipsoid algorithm and simultaneous diophantine approximation. As a side result, we prove that the set of assignments at equilibria is convex and the equilibria prices themselves are log-convex. Our convex program is explicit and intuitive, which allows maximizing a concave function over the set of equilibria. On the practical side, Ye developed an interior point algorithm (Ye, 2004) to find an equilibrium based on our convex program. We also derive separate combinatorial characterizations of equilibrium for Arrow-Debreu and Fisher cases. Our convex program can be extended for many non-linear utilities (Codenotti and Varadarajan, 2004; Jain and Ye) and production models (Jain). Our paper also makes a powerful theorem even more powerful in the area of geometric algorithms and combinatorial optimization. The main idea in this generalization is to allow ellipsoids not to contain the whole convex region but a part of it. This theorem is of independent interest.

Efficient integration of a multi-hop wireless network with the Internet is an important research problem. In a wireless neighborhood network, a few Internet transit access points (ITAPs), serving as gateways to the Internet, are deployed across the neighborhood; houses are equipped with low-cost antennas, and form a multi-hop wireless network among themselves to cooperatively route traffic to the Internet through the ITAPs. Furthermore, the placement of Internet TAPs is a critical determinant of system performance and resource usage. We explore the placement problem under three wireless link models. For each link model, we develop algorithms to make informed placement decisions based on neighborhood layouts, user demands, and wireless link characteristics. We also extend our algorithms to provide fault tolerance and handle significant workload variation. We evaluate our placement algorithms and show that our algorithms yield close to optimal solutions over a wide range of scenarios we have considered.

Network coding solutions and routing solutions, namely packing distribution trees, for the problem of information multicast is compared in this paper. To enable the comparison, we develop greedy tree packing algorithms that repeatedly pack the maximum-rate distribution tree and a greedy tree packing algorithm based on Lovasz' proof to Edmonds' theorem. We then investigate the potential advantages of network coding over routing. In terms of throughput, tree packing performs comparably to network coding on the network graphs of six Internet service providers. However, network coding offers additional benefits, including fewer network resources consumed, ease of management, and robustness.

In this paper, we address the following question: given a specific placement of wireless nodes in physical space and a specific traffic workload, what is the maximum throughput that can be supported by the resulting network? Unlike previous work that has focused on computing asymptotic performance bounds under assumptions of homogeneity or randomness in the network topology and/or workload, we work with any given network and workload specified as inputs.A key issue impacting performance is wireless interference between neighboring nodes. We model such interference using a conflict graph, and present methods for computing upper and lower bounds on the optimal throughput for the given network and workload. To compute these bounds, we assume that packet transmissions at the individual nodes can be finely controlled and carefully scheduled by an omniscient and omnipotent central entity, which is unrealistic. Nevertheless, using ns-2 simulations, we show that the routes derived from our analysis often yield noticeably better throughput than the default shortest path routes even in the presence of uncoordinated packet transmissions and MAC contention. This suggests that there is opportunity for achieving throughput gains by employing an interference-aware routing protocol.

In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O ( m log m ) and O ( n 3 ), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.

We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. We use this algorithm to find better approximation algorithms for the capacitated facility location problem with soft capacities and for a common generalization of the k-median and facility location problems. We also prove a lower bound of 1+2/e on the approximability of the k-median problem. At the end, we present a discussion about the techniques we have used in the analysis of our algorithm, including a computer-aided method for proving bounds on the approximation factor.

Perhaps the strongest notion of truth-revealing in a cost sharing method is group strategyproofness. However, matters are not so clear-cut on fairness, and many different, sometimes even conflicting, notions of fairness have been proposed which have relevance in different situations. We present a large class of group strategyproof cost sharing methods, for submodular cost functions, satisfying a wide range of fairness criteria, thereby allowing the service provider to choose a method that best satisfies the notion of fairness that is most relevant to her application. Our class includes the Dutta-Ray egalitarian method as a special case. It also includes a new cost sharing method, which we call the opportunity egalitarian method.

In the survivable network design problem (SNDP), given an undirected graph and values r/sub ij/ for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r/sub ij/ disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. K. Jain et al. (1999) propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max/sub i,j/ r/sub ij/. VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r/sub ij//spl isin/{0, 1, 2}. She also shows that the same techniques will not work for VC-SNDP for more general values of r/sub ij/. The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures.

The Internet, which is intrinsically a common playground for a large number of players with varying degrees of collab-orative and selsh motives, naturally gives rise to numerous new game theoretic issues. Computational problems under-

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k -median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m ) and O(m log m(L + log ( n ))) respectively, where n and m are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m) and O(m log m(L+log(n))) respectively, where n and m are the total number of vertices and edges in the underlying graph. The main algorithmic idea is a new extension of the primal-dual schema.

We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem.

The problem of minimizing the trellis complexity of a code by coordinate permutation is studied. Three measures of trellis complexity are considered: the total number of states, the total number of edges, and the maximum state complexity of the trellis. The problem is proven NP-hard for all three measures, provided the field over which the code is specified is not fixed. We leave open the problem of dealing with the case of a fixed field, in particular GF(2).