BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Alejandro López-Ortiz

Alejandro López-Ortiz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational GeometryDiscrete MathematicsNetworking and Internet Architecture

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2014arXiv

An All-Around Near-Optimal Solution for the Classic Bin Packing Problem

In this paper we present the first algorithm with optimal average-case and close-to-best known worst-case performance for the classic on-line problem of bin packing. It has long been observed that known bin packing algorithms with optimal average-case performance were not optimal in the worst-case sense. In particular First Fit and Best Fit had optimal average-case ratio of 1 but a worst-case competitive ratio of 1.7. The wasted space of First Fit and Best Fit for a uniform random sequence of length $n$ is expected to be $Θ(n^{2/3})$ and $Θ(\sqrt{n} \log ^{3/4} n)$, respectively. The competitive ratio can be improved to 1.691 using the Harmonic algorithm; further variations of this algorithm can push down the competitive ratio to 1.588. However, Harmonic and its variations have poor performance on average; in particular, Harmonic has average-case ratio of around 1.27. In this paper, first we introduce a simple algorithm which we term Harmonic Match. This algorithm performs as well as Best Fit on average, i.e., it has an average-case ratio of 1 and expected wasted space of $Θ(\sqrt{n} \log ^{3/4} n)$. Moreover, the competitive ratio of the algorithm is as good as Harmonic, i.e., it converges to $ 1.691$ which is an improvement over 1.7 of Best Fit and First Fit. We also introduce a different algorithm, termed as Refined Harmonic Match, which achieves an improved competitive ratio of $1.636$ while maintaining the good average-case performance of Harmonic Match and Best Fit. Finally, our extensive experimental evaluation of the studied bin packing algorithms shows that our proposed algorithms have comparable average-case performance with Best Fit and First Fit, and this holds also for sequences that follow distributions other than the uniform distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient Online Strategies for Renting Servers in the Cloud

In Cloud systems, we often deal with jobs that arrive and depart in an online manner. Upon its arrival, a job should be assigned to a server. Each job has a size which defines the amount of resources that it needs. Servers have uniform capacity and, at all times, the total size of jobs assigned to a server should not exceed the capacity. This setting is closely related to the classic bin packing problem. The difference is that, in bin packing, the objective is to minimize the total number of used servers. In the Cloud, however, the charge for each server is proportional to the length of the time interval it is rented for, and the goal is to minimize the cost involved in renting all used servers. Recently, certain bin packing strategies were considered for renting servers in the Cloud [Li et al. SPAA'14]. There, it is proved that all Any-Fit bin packing strategy has a competitive ratio of at least $μ$, where $μ$ is the max/min interval length ratio of jobs. It is also shown that First Fit has a competitive ratio of $2μ+ 13$ while Best Fit is not competitive at all. We observe that the lower bound of $μ$ extends to all online algorithms. We also prove that, surprisingly, Next Fit algorithm has competitive ratio of at most $2 μ+1$. We also show that a variant of Next Fit achieves a competitive ratio of $K \times max\{1,μ/(K-1)\}+1$, where $K$ is a parameter of the algorithm. In particular, if the value of $μ$ is known, the algorithm has a competitive ratio of $μ+2$; this improves upon the existing upper bound of $μ+8$. Finally, we introduce a simple algorithm called Move To Front (MTF) which has a competitive ratio of at most $6μ+ 7$ and also promising average-case performance. We experimentally study the average-case performance of different algorithms and observe that the typical behaviour of MTF is distinctively better than other algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Advice Complexity of the k-server Problem under Sparse Metrics

We consider the k-server problem under the advice model of computation when the underlying metric space is sparse. On one side, we show that an advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of size n, even for the 2-server problem on a path metric of size N >= 5. Through another lower bound argument, we show that at least (n/2)(log α - 1.22) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 <= α < 2k. On the other side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs, which require advice of (almost) linear size. Namely, we show that for graphs of size N and treewidth α, there is an online algorithm which receives $O(n (log α + log log N))$ bits of advice and optimally serves a sequence of length n. With a different argument, we show that if a graph admits a system of μ collective tree (q,r)-spanners, then there is a (q+r)-competitive algorithm which receives O(n (log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, provided with O(n log log N) bits of advice.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Online Bin Packing with Advice

We consider the online bin packing problem under the advice complexity model where the &#39;online constraint&#39; is relaxed and an algorithm receives partial information about the future requests. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with log n + o(log n) bits of advice, achieves a competitive ratio of 3/2 for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives 2n + o(n) bits of advice and achieves a competitive ratio of 4/3 + ε. Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

FIFO Queueing Policies for Packets with Heterogeneous Processing

We consider the problem of managing a bounded size First-In-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Our objective is to maximize the total number of successfully transmitted packets. We consider both push-out (when the policy is permitted to drop already admitted packets) and non-push-out cases. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study which experimentally validates the predicted theoretical behaviour.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Some New Equiprojective Polyhedra

A convex polyhedron $P$ is $k$-equiprojective if all of its orthogonal projections, i.e., shadows, except those parallel to the faces of $P$ are $k$-gon for some fixed value of $k$. Since 1968, it is an open problem to construct all equiprojective polyhedra. Recently, Hasan and Lubiw [CGTA 40(2):148-155, 2008] have given a characterization of equiprojective polyhedra. Based on their characterization, in this paper we discover some new equiprojective polyhedra by cutting and gluing existing polyhedra.

0 citations0 reviewsNo code linkedOpen access